Hybrid associative memory and method for the retrieval and sorting of data contained therein

专利摘要:

公开号:WO1984003970A1
申请号:PCT/DE1984/000072
申请日:1984-03-29
公开日:1984-10-11
发明作者:Gerhard Wolf
申请人:Siemens Ag；
IPC主号:G06F7-00

专利说明:
[0001] HYBRID ASSOZIATIVSPEICHER SOWIE VERFAHREN ZUM AUFSUCHEN UND SORTIEREN DAREIN
[0002] Die Erfindung betrifft einen Hybrid-Assoziativspeicher, bestehend aus einem nicht assoziativen Basisspeicher und einer assoziativen Oberfläche.
[0003] Derartige Hybrid-Assoziativspeicher sind bereits in vielen Ausführungsformen bekannt, zum Beispiel durch "Electronics", August 17, 1970, Seiten 96 bis 100; DE-AS 25 25 287; "data report" 11 (1976), Heft 2, Seiten 29 bis 34, insbesondere Bild 3c; europäische Patentanmeidung EP-A2-0035787; deutsche Offenlegungsschrift
[0004] DE-OS 32 16 905, wenn man bei letzterer unterstellt, daß die Speicherregister der assoziativen Speicherzellen aus einem anderen Speicher geladen werden; die US-Patentschriften 3.648.254, 4.145.737, 4.149.262, 4.144.564 und 4.257.110.
[0005] Der Vorteil solcher Hybrid-Assoziativspeicher gegenüber reinen Assoziativspeichern besteht vor allem in der kostengünstigeren Speicherung großer Datenmengen, die im Rahmen von Such- und Sortierverfahren assozitiv zu überprüfen sind.
[0006] Die Leistungsfähigkeit dieser bekannten Anordnungen ist jedoch immer noch nicht ausreichend. So werden von den assoziativen Verknüpfungseinheiten mit einer der Speicherbreite entsprechenden Arbeitsbreite nur ganze SpeiKt 1 Stl / 31.01.84 cherzeilen bzw. Worteinheiten erfaßt. Die bei Datenverarbweitungsanlagen übliche Unterteilung der zu verarbeitenden Dateneinheiten in Subeinheiten, z.B. als Doppelworte zu je acht Byte mit je acht Bit oder als Einfachworte zu je vier Byte mit je acht Bit, kann daher nur durch eine entsprechende Maskenabdeckung in den assoziativen Verknüpfungseinheiten berücksichtigt werden, so daß ein Großteil der assoziativen Oberfläche vielfach nicht genutzt werden kann.
[0007] Weitere die Leistung einschränkende Nachteile ergeben sich aus der Art der die assoziative Oberfläche bildenden Verknüpfungseinheiten, die vielfach nur reine Vergleichsfunktionen ausführen können.
[0008] Bei der durch die genannte DE-OS 32 16 905 bekannten Anordnung bestehen die den Verknüpfungseinheiten entsprechenden Assoziativspeicherzellen jeweils aus einem Operationswerk, das sich in ein Assoziationswerk zur Durchführung der Assoziationsrelationen und ein nachgeschaltetes Verarbeitungswerk zur Durchführung von Verknüpfungsoperationen bei Vorliegen einer Trefferanzeige durch das zugehörige Assoziationswerk gliedert. Dabei besteht das Assoziationswerk im wesentlichen aus einem Vergleicher und ggf. einem Antivalenzprüfnetzwerk mit Zähler zur Ermittlung eines Abstandswertes auf Bitebene und das Verarbeitungsnetzwerk aus einer arithmetisch-logischen Einheit. Beide Werke sind zudem maskierbar, so daß bei Bedarf ausgewählte Bereiehe der jeweils bereitstehenden Dateneinheit verarbeitet werden können.
[0009] Ein derartiger Aufbau der Assoziativspeicherzelle als Verknüpfungseinheit einer assoziativen Oberfläche ist einerseits recht aufwendig, und andererseits ist die Anzahl der durchführbaren Assoziationsrelationen sehr stark vom jeweiligen Aufbau des gesonderten Assoziationswerkes abhängig. Des weiteren ist der erforderliche Zeitaufwand für die Durchführung verschiedener Aufgaben, wie z.B. das Suchen anhand eines die Arbeitsbreite der Verknüpfungseinheit übersteigenden Suchargumentes, zu groß, da für die Trefferverknüpfung der einen Globaltreffer bewirkenden Teiltreffer je Verknüpfungseinheit bei der bekannten Anordnung nach jeder durchgeführten Assoziationsrelation auf einen gesonderten Elementarzyklus für das Verarbeitungswerk umgeschaltet werden müßte, soweit an derartige Aufgaben bei der bekannten Anordnung überhaupt gedacht ist, da das Verarbeitungswerk nur trefferabhängig aufgrund einer vorangehend durchgeführten Assoziationsrelation arbeitet.
[0010] Schließlich spielt die Ausrichtung der Datenfolgen in vertikaler oder horizontaler Richtung bezüglich der Leistungsfähigkeit des Hybrid-Assoziativspeichers eine entscheidende Rolle. Allgemein wird die horizontale Ausrichtung bevorzugt, weil sie leichter zu realisieren ist. Jedoch begrenzt dann die Speicherbreite die Länge der Datenfolgen, wenn man nicht mehrere Zeilen ketten will. Da Speicherungsstruktur und die durchzuführenden Such- und Sortierverfahren zum Teil abhängig voneinander sind, sind auch die meisten dieser Verfahren auf die horizontale Ausrichtung der Daten aufgestellt, so z.B. auch das aus der deutschen Patentschrift 23 42 660 bzw. der bereits genannten europäischen Patentanmeldung EP-A2-0035787 bekannte Sortierverfahren.
[0011] Aufgabe der Erfindung ist es daher, einen Hybrid-Assoziativspeicher der eingangs genannten Art zu schaffen, - der bei größerer Anpassungsfähigkeit eine wesentlich höhere Leistungsfähigkeit beim assoziativen Betrieb aufweist, ohne daß die Eigenschaften eines normalen ZugriffSpeichers (RAM) dadurch verlorengehen,
[0012] - bei dem bei geringerem Aufwand für die einzelnen Verknüpfungseinheiten der assoziativen Oberfläche der
[0013] Umfang der durchführbaren Assoziationsrelationen wesentlich erweitert ist und
[0014] - bei dem gleichzeitig die Voraussetzung zum weitgehend selbständigen Arbeiten der bei der Durchführung verschiedener Aufgaben, z.B. Suchen oder Sortieren von Daten, infolge einer Mischung von durchzuführenden Assoziationsrelationen und beliebigen Verknüpfungsfunktionen arithmetischer oder logischer Art mit einer Vielzahl von wähl weisen möglichen Zuordnungen der einzelnen Bausteine in den Verknüpfungseinheiten in wenig Zeit erfordernder Weise eröffnet wird, sowie Such- und Sortiarverfahren dafür so zu gestalten, - daß die durch den neuen Hybrid-Assoziativspeicher vorgegebenen Randbedingungen zweckmäßig genutzt werden, insbesondere beim Suchen in nicht ausgerichteten, d.h. nicht gleich langen, Daten und beim Sortieren von großen ausgerichteten Datenmengen ohne Beschränkung der einzelnen Datenfolgen.
[0015] Ausgangspunkt zur Lösung dieser Aufgabe ist die neuartige Gestaltung des Sasisspeichers gemäß Patentanspruch 1, der die in Datenverarbeitungsanlagen übliche Unterteilung von zu verarbeitenden Daten, z.B. Datenwörter, in Subeinheiten, z.B. Byte, berücksichtigt und dementsprechend die Verwendung von Verknüpfungseinheiten jeweils nur mit einer den Subeinheiten entsprechenden Arbeitsbreite. Das schafft die Voraussetzung, daß die einzelnen Subeinheiten unabhängig voneinander überprüft werden können und daß zu deren Überprüfung nicht die gesamte übrige Wortbreite maskiert werden muß und damit Teile der assoziativen Oberfläche für assoziative Relationsverknüpfungen weitgehend blockiert werden. Des weiteren ist damit eine auf Teilbereiche in Form von vertikalen Feldern beschränkte Mischung der jeweils für sich bekannten vertikalen und horizontalen Speicherung verbunden. Dadurch wird in Verbindung mit einer entsprechend ausgebildeten Auswahlsteuerung sichergestellt, daß wahlweise, nämlich abhängig vom normalen oder vom assoziativen Speicherbetrieb, entweder alle Subeinheiten einer Dateneinheit oder alle miteinander korrespondierenden Subeinheiten aller Dateneinheiten eines Feldes gleichzeitig gelesen bzw. eingeschrieben werden können, wobei Umordnungseinrichtungen im jeweiligen Datenflußweg dafür sorgen, daß jeweils die richtige Reihenfolge der Subeinheiten wieder hergestellt bzw. die für die Speicherung erforderliche Umordnung vorgenommen wird.
[0016] Entsprechend kann die assoziative Oberfläche sowohl jede Dateneinheit als solche als auch bei voller Ausnutzung der assoziativen Oberfläche eine entsprechende Anzahl von miteinander korrespondierenden Subeinheiten mehrerer Dateneinheiten gleichzeitig überprüfen, als wären z.B. mehrere Datenwörter nebeneinander in Form von vertikalen Bytesäulen gespeichert.
[0017] Weiterbildungen entsprechend einer Reihe weiterer Patentansprüche beziehen sich auf die vorteilhafte Art der Einordnung der Subeinheiten im Basisspeicher, auf die Ausgestaltung einzelner Steuereinrichtungen, wie Adressen- und Datenumordner, auf die Gestaltung der Datenflußwege, auf die modulartige Erweiterung des Grundbausteins, sowie auf zusätzliche Steuerungsmaßnahmen zur weiteren Steigerung der Leistungsfähigkeit durch Maskierung der Auswahlsteuerung oder durc h Streamen der Dateneinheiten beim Laden oder Leeren des Basisspeichers.
[0018] In Verbindung mit dieser neuartigen Gestaltung des Basisspeichers bezieht sich eine Reihe weiterer Patentansprüche auf die Ausbildung der assoziativen Oberfläche für den Basisspeicher. So ist nach Patentanspruch 17 Kernstück einer jeden Verknüpfungseinheit der assoziativen Oberfläche des neuen Hybrid-Assoziativspeichers jeweils eine einzige arithmetisch-logische Einheit (ALU) in Verbindung mit den üblichen Operanden- und Ergebnisregistern, die wahlweise sowohl für die Durchführung von Assoziationsrelationen als auch für die Durchführung von arithmetischen und logischen Verknüpfungsfunktionen benutzt wird. Die Treffer- bzw. Nichttreffersignale bei der Durchführung von Assoziationsrelationen werden dabei von den Anzeigen der ALU abhängig von der jeweils durchgeführten Assoziationsrelation abgeleitet.
[0019] Der Aufwand für die einzelnen Verknüpfungseinheiten ist gering. Andererseits können die Verknüpfungseinheiten universell für die unterschiedlichsten Aufgaben herangezogen werden. Insbesondere ermöglichen die einzelnen Verknüpfungseinheiten in Verbindung mit einer Zuführung von individuellen Datenfolgen entsprechend einer vertikalen Ausrichtung im Basisspeicher eine Überprüfung mit längeren Suchargumenten, ohne daß nach jeder durchgeführten Assoziationsrelation ein zusätzlicher Elementarzyklus für die Durchführung einer Verknüpfungsfunktion mit der ALU eingeschoben werden muß. Die je Zeichen einer Datenfolge erzielten Teiltreffer können vielmehr innerhalb jeder Verknüpfungseinheit unmittelbar gekettet werden, um einen Globaltreffer zu ermitteln. Dafür genügt beispielsweise eine einzige zusätzliche bistabile Kippstufe, die bei einem Nichttreffer in Folge zurückgestellt wird und damit z.B. eine Suchfolge abbrechen und auf die nachfolgende Suchfolge im Rahmen eines Suchvorganges umschalten läßt.
[0020] Durch zusätzliche Elemente, wie eine Einrichtung zur Bildung von Quersummen am Ausgang der ALU, durch die Einschaltung zusätzlicher Schiebemöglichkeiten im ALU-Kreislauf können Untersuchungen auf Ähnlichkeiten, Treffergewichtungen und ähnliche Funktionen innerhalb jeder Verknüpfungseinheit direkt vorgenommen werden.
[0021] Insbesondere kann durch ein zusätzliches Maskenregister in Verbindung mit einer Maskensteuerung je Verknüpfungseinheit eine individuelle oder aber eine von außen gesteuerte globale Bitmaskierung vorgenommen werden.
[0022] Bezogen auf einen derartigen Hybrid-Assoziativspeicher lassen sich auch Such- und Sortierverfahren entsprechend einer Reihe weiterer Patentansprüche vorteilhafter gestalten. So eröffnet Patentanspruch 46 die Möglichkeit, daß nach einem einheitlichen Verfahren mehrere vertikale Datenfolgen gleichzeitig überprüft werden können, so daß eine durch die Datenfolgen insgesamt vorgegebene Datenmenge beispielsweise schneller überprüft werden kann. Dabei braucht der Suchvorgang erst dann abgebrochen zu werden, wenn für keine der gleichzeitig überprüften Datenfolgen ein Treffer angezeigt wird. Letzteres kann in einfacher Weise von der mit der assoziativen Oberfläche in üblicher Weise gekoppelten Trefferauswertung überwacht werden, ohne daß ein Eingriff in die Anordnungen für die Trefferkettung erforderlich ist. Alle Verknüpfungseinheiten der assoziativen Oberfläche werden dabei einheitlich von einer Quelle, z.B. von einer übergeordneten Speichersteuerung aus, mit den notwendigen Parametern und den Steuerbefehlen versorgt und damit global gesteuert, unabängig davon, ob für einzelne der Datenfolgen die Trefferkettungen bereits abgerissen sind, wenn nur für wenigstens eine der Datenfolgen die Trefferkettung noch aufrechterhalten ist.
[0023] Auch Kettungen von gleich langen Datenteilfolgen lassen sich dabei ohne wesentlichen Mehraufwand bewältigen.
[0024] Weiterhin eröffnet Patentanspruch 48 die Möglichkeit zur Anwendung des durch die deutsche Patentschrift 23 42 660 bekannten vorteilhaften Sortierverfahrens und damit die Sortierung auch großer Datenmengen ohne Beschränkung der Länge der einzelnen Datenfolgen mit annehmbaren Zeitaufwand. So ist zum einen allein durch die Ausnutzung der Adressensteuerung eine Beschränkung auf die für die Sortierung maßgeblichen Daten möglich, ohne daß die Leistungsfähigkeit der assoziativen Oberfläche infolge Maskierung von Teilbereichen eingeschränkt wird. Damit außerdem bei über die Arbeitsbreite der einzelnen Verknüpfungseinheiten der assoziativen Oberfläche hinausgehenden Sortierbitmustern einwandfreie Ergebnisse erzielt werden, werden vollständige Zeichen oder Bytes des Sortierbitmustes zwischengespeichert und Zusatzmaßnahmen für die Herstellung von Trefferkettungen für aufeinanderfolgende Datenzeichen eines Datums und für die Überwachung der jeweiligen Kettungsbedingungen durchgeführt. Dazu können individuelle-Kettungselemente je Datum verwendet werden, so daß die Kettungsbedingung im Rahmen einer Erweiterung des Sortierbitmusters nicht immer erst wieder ermittelt werden muß.
[0025] Abhängig von der Art der Kettungselemente und deren Aussage kann auch der Zeitaufwand für die Ermittlung der Kettungsbedingungen beim Unterschreiten von Bytegrenzen im Rahmen einer Einengung des Sortierbitmusters in unterschiedlicher Weise herabgesetzt werden.
[0026] Unabhängig davon läßt sich der Zeitaufwand für die einzelnen Suchläufe durch Prüfung aller Daten mit einem vorgegebenen Sortierbitmuster durch zusätzliche Maßnahmen in unterschiedlicher Weise beeinflussen. Diese Maßnahmen bestehen u.a. in einer gleichzeitigen Prüfung mehrerer Daten durch eigene Verknüpfungseinheiten der assoziativen Oberfläche, im Abbruch eines Suchlaufes nach Auftreten eines zweiten Treffers oder Mehrfachtreffers, der sowieso einen weiteren Suchlauf mit Ausweitung des Sortierbitmusters erfordert, oder in der Markierung von durch Treffer gekennzeichneten Daten und Wertung von Treffern lediglich von markierten Daten im folgenden Suchlauf bzw. Beschränkung des folgenden Suchlaufs lediglich auf die markierten Daten. Eine andere Maßnahme besteht in der Verwendung eines assoziativen Hilfsspeichers, der zweckmäßig in den BasisSpeicher des Hybrid-Assoziativspeichers integriert ist, und der die bei einem Suchlauf durch Treffer gekennzeichneten Daten übernimmt und in einem auf diese Daten beschränkten anschließenden Sortiervorgang durch die assoziative Oberfläche.
[0027] Abhängig von der Art und vom Umfang der vom Hybrid-Assoziativspeicher ausführbaren assoziativen Funktionen kann die Prüfung der einzelnen Daten bzw. Datenzeichen anhand des zur Verfügung stehenden Sortierbitmusters auf verschiedene Art durchgeführt werden: Es wird die Gleichheit zwischen dem Sortierbitmuster und den entsprechenden Datenbits geprüft, wobei die nicht relevanten Bitstellen der für die Ausführung der Assoziationsfunktion zur Verfügung stehenden Arbeitsbreite durch eine Maske abgedeckt und daher beim Vergleich nicht berücksichtigt werden, oder aber man verzichtet auf die Maskensteuerung für die Festlegung des jeweiligen Assoziationsbereiches im Bereich der Arbeitsbreite und wertet die assoziative Aussage "KLEINER/GLEICH" beim Vorwärts- oder Aufwärtssortieren bzw. "GRÖSSER/GLEICH" beim Rückwärts- oder Abwärtssortieren über die gesamte Arbeitsbreite, wobei das jeweilige Sortierbitmuster für den Rest der zur Verfügung stehenden Arbeitsbreite durch lauter "1" bzw. "0" aufgefüllt wird.
[0028] Auch erlaubt das Verfahren in sehr einfacher Weise Varianten zum Aufsuchen von Einzeldaten bzw. einer vorgegebenen Anzahl von Daten mit zu einem vorgegebenen Wert am nächsten liegenden Wert sowie zum Aufsuchen von Daten mit dem höchsten oder dem niedrigsten Wert bzw. den n höchsten oder niedrigsten Werten innerhalb einer Datenmenge.
[0029] Nachfolgend sei die Erfindung anhand von in der Zeichnung dargestellten Ausführungsbeispielen näher erläutert. Im einzelnen zeigen
[0030] FIG 1 ein Prinzipschaltbild des Hybrid-Assoziativspeichers gemäß der Erfindung mit nur einer Speichergruppe für den Basisspeicher,
[0031] FIG 2 ein Prinzipschaltbild der zugehörigen Adressensteuerung,
[0032] FIG 3 drei Ausführungsbeispiele für den Adressenumordbis 5 ner in Form von Prinzipschaltbildern,
[0033] FIG 6 ein Prinzipschaltbild zur Erläuterung der Einfügung von Datenumordnern in die verschiedenen Datenflußwege,
[0034] ein Prinzipschaltbild der mit der Adressensteuerung von FIG 2 koppelbaren Adressenmaskensteuerung,
[0035] den prinzipiellen Aufbau eines Basisspeichers entsprechend FiG 1 bei Verwendung mehrerer Speichergruppen mit gemeinsamem Adressenumordner,
[0036] die Kopplung eines Pufferspeichers mit dem Basisspeicher von FIG 8. in prinzipieller Darstellung,
[0037] den Aufbau einer Verknüpfungseinheit als Baustein der assoziativen Oberfläche,
[0038] den prinzipiellen Aufbau der Treffersteuerung von FIG 10,
[0039] den prinzipiellen Aufbau der Maskensteuerung von
[0040] FIG 10,
[0041] ein Prinzipschaltbild zur Erläuterung der bei geketteten Datenteilfolgen möglicherweise notwendig werdenden Umschaltung für die Trefferkettung,
[0042] einen Teilausschnitt der Trefferauswertesteuerung bei Ausführung der Trefferkettung von geketteten Datenteilfolgen,
[0043] ein Flußdiagramm zur Erläuterung des Verfahens zum Aufsuchen von Daten in einem Hybrid-Assoziativspeicher, FIG 16 das beim Suchen und Sortieren von Daten verwendete Änderungsschema für das Sortierbitmuster,
[0044] FIG 17 eine Tabelle für die Entwicklung des Sortierbitmusters beim Sortieren von drei vorgegebenen Daten entsprechend dem in FIG 16 gezeigten Änderungsschema,
[0045] FIG 18A ein Ablaufdiagramm für einen Sortiervorgang bis 18C ohne Verwendung von individuellen Kettungselementen je Datum der zu prüfenden Datei,
[0046] FIG 19A ein Ablaufdiagramm in Anlehnung an das von und 19B FIG 18A bis 18C bei Verwendung von individuellen Kettungselementen je Datum der zu prüfenden Datei,
[0047] FIG 20 die Gegenüberstellung dreier Daten zur Erläuterung des Ungültigwerdens der in den individuellen Kettungselementen enthaltenen
[0048] Kettungsaussagen bei Unterschreiten einer Bytegrenze des Sortierbitmusters,
[0049] FIG 21 den prinzipiellen Aufbau einer Anordnung zur Durchführung des Sortierverfahrens gemäß der
[0050] Erfindung,
[0051] FIG 22 ein Prinzipschaltbild für die Kettungssteuerung bei Verwendung individueller Kettungselemente für eine Ein-Bit-Aussage,
[0052] FIG 23 ein Prinzipschaltbild für die Kettungssteuerung bei Verwendung von Kennzahlen speichernden Kettungselementen und FIG 24 ein Prinzip sc haltbil d des ge sam ten Aufbaus eines Hy brid-Assoziativspeichers f ür gro ße Datenmengen in Anl ehnung an die in den übrigen Figuren gezeigten B auteil e .
[0053] Der in FIG 1 gezeigte Hybrid-Assoziativspeicher gliedert sich in herkömmlicher Weise in einen normalen Zugriffsspeicher als Basisspeicher B-SP und eine assoziative Oberfläche ASS-FL mit einer TrefferauswerteSteuerung T-AUSW.
[0054] Der Basisspeicher B-SP hat eine einer Dateneinheit entsprechende Arbeitsbreite, wobei in herkömmlicher Weise die Dateneinheiten säulenförmig untereinander einschreibbar und auslesbar sind und jede Speicherzeile zur Auswahl einer Dateneinheit einzeln ansteuerbar ist. Jede Dateneinheit ist in Subeinheiten unterteilt;im vorliegenden Falle sind als Dateneinheiten Wörter mit je 4 Byte zu je 8 Bit zugrundegelegt. Abhängig von der Arbeitsbreite des angeschlossenen Datenleitungssystems könnten es auch Doppelwörter mit je 8 Byte sein.
[0055] Entsprechend gliedert sich der Basisspeicher B-SP in eine entsprechende Anzahl von vertikalen Bytespalten, die bei der Auswahl einer Dateneinheit oder eines Wortes durch eine zeilenorientierte Zugriffsadresse AD gleichzeitig angesteuert werden, beispielsweise die Dateneinheit AOi mit den 4 Bytes AOO, AO1, AO2, AO3 in der ersten Speicherzeile.
[0056] Nun sind aber aus noch zu erläuternden Gründen die einzelnen Wörter nicht in gleicher Weise in den einzelnen Speicherzeilen angeordnet, sondern die Anordnung folgt einem vorgegebenen Einordnungsschema, demzufolge es möglich ist, bei einem Speicherzugriff entweder die vier Bytes eines Wortes in herkömmlicher Weise oder aber die miteinander korrespondierenden Bytes mehrerer vertikal aufeinanderfolgender Wörter gleichzeitig in Form eines Wortes auszulesen.
[0057] Entsprechend den gewählten vier Bytes in jeder Speicherzeile bilden daher entsprechend viele Dateneinheiten oder Wörter jeweils ein Speicherfeld F, z.B. die Wörter AOi, BOi, COi und DOi für das Feld FO, das durch einen Feldadressteil F-AD = 0 innerhalb der Zugriffsadresse AD ansteuerbar ist. Von Speicherzeile zu Speicherzeile werden dabei die miteinander korrespondierenden Bytes aller Wörter im Feld, also z.B. AOO, BOO, COO und DOO für das Feld FO, zyklisch um ein Byte versetzt angeordnet, so daß die miteinander korrespondierenden Bytes aller Wörter im Feld jeweils auf einer Diagonale liegen, wobei die einzelnen Diagonalen zyklisch umlaufen.
[0058] Damit dennoch der herkömmliche Zugriffmechanismus zu den einzelnen Dateneinheiten in den einzelnen Dateneinheitsebenen oder Speicherzeilen nach außen aufrecht erhalten werden kann, ist für den Zeilenadreßteil Z-AD als weiterer Bestandteil der Zugriffadresse AD neben dem Feldadreßteil F-AD eine Umordnung innerhalb der Adressensteuerung AD-ST erforderlich, indem jede Bytespalte des Feldes gesondert mit einer gesonderten Zeilenadresse angesteuert wird. Dies läßt sich ohne Schwierigkeit realisieren, wenn man für die einzelnen Bytespalten getrennte Speicherbausteine verwendet, was für einen Basisspeicher B-SP größerer Speicherkapazität ohnehin unumgänglich ist.
[0059] FIG 2 zeigt den prinzipiellen Aufbau eines Doppelfeldes FO/1 im Basisspeicher mit vier Speicherbausteinen als Bytespaltenmodule BSP-MD0 bis BSP-MD3. Jeder dieser Bausteine hat ein Fassungsvermögen von z.B. acht Byte, die in zwei Gruppen zu je vier Bytezeilen BZ0 bis BZ3 gegliedert sind, und jeder Baustein ist mit einer Bytezeilenauswahlsteuerung BZ-AW gekoppelt, über die die Ansteuerung beim Lesen oder Schreiben eines Bytes erfolgt. Liegen die ein Wort bildenden vier Bytes in einer Dateneinheitsebene, z.B. in der Bytezeile BZ0, dann wird allen Speicherbausteinen BSP-MD... dieselbe Zeilenadresse Z-AD_(BSP...) zugeführt. Liegen die ein Wort bildenden Bytes jedoch diagonal versetzt in unterschiedlichen Daeneinheitsebenen, dann erhalten alle Speicherbausteine unterschiedliche Zeilenadressen
[0060] Z-AD_(BSP0) bis Z-AD_(BSP3), wobei in beiden Fällen die Gruppenauswahl je Speicherbaustein durch die gesamte oder einen Teil der Feldadresse F-AD gesteuert wird.
[0061] Beim gewählten Ausführungsbeispiel genügen zur Unterscheidung der vier jeweils ein Speicherfeld F... im Basisspeicher B-SP bildenden Speicherzeilen zwei Bit, nämlich X und Y, die die Zeilenadresse Z-AD im Feld bildet. Diese zusammen mit der Feldadresse F-AD in einem Adressenregister AD-REG gespeicherten Zeilenadreßbits werden einem Adressenumordner AD-UM zugeführt, der abhängig vom gewählten Betriebsmodus MOD die benötigten Einzeladressen Z-AD_(BSP...) bereitstellt.
[0062] Bei dem sich aus dem Speicherfeld F0 des Basisspeichers B-SP in FIG 1 ergebenden Einordnungsschema liegen alle eine Dateneinheit bildenden Bytes in einer Ebene, nur die Reihenfolge der Bytes innerhalb der einzelnen Wörter ist zyklisch vertauscht. Insbesondere beim normalen Speicherbetrieb sind daher jeweils alle in einer Zeile liegenden Bytes anzusteuern, was ein und dieselbe Zeilenansteueradresse Z-AD_(BSP...) in FIG 2 erfordert, während beim Lesen bzw. Schreiben von Dateneinheiten, die aus den miteiander korrespondierenden Bytes aller Wörter im Feld zusammengesetzt werden, für jede Bytespalte unterschiedliche Zeilenadressen Z-AD_(BSP0) bis Z-AD_(BSP3) zur Verfügung zu stellen sind, und zwar abhängig von dem die zugehörige Dateneinheitsebene im Basisspeicher B-SP kennzeichnenden Zeilenadreßteil Z-AD der Zugriffsadresse AD.
[0063] FIG 3 zeigt in Form eines Prinzipschaltbildes einen Adressenumordner AD-UM, wie er in FIG 2 verwendet werden kann. Dieser Adressenumordner besteht aus vier Modulo-4 arbeitenden 2-Bit-Subtrahierern SUB1 bis SUB4, denen als Subtrahend die Ausgangszeilenadresse Z-AD zugeführt wird. Der Minuend besteht jeweils aus einer der möglichen vier Basisadessen "0", "1", "2" oder "3", deren Zuschaltung entsprechend den beiden Modusarten MOD durch Multiplexer MUX gesteuert wird. Im Normalbetrieb des Basisspeichers B-SP ist der Minuend in Form der Basisadresse "0" für alls Subtrahierer gleich, so daß sich für alle Bytespalten gleiche Zeilenadressen Z-AD_(BSP...) ergeben. Bei der anderen Betriebsart wird die Zeilenadresse Z-AD jeweils von einer der möglichen Basissadressen abgezogen, so daß sich vier unterschiedliche Zeilenadressen ZAD_(BSP0) bis Z-AD_(BSP3) entsprechend der Moculo-4-Verschiebung ergeben. Mit fortlaufender Zeilenadresse Z-AD im Feld verschiebt sich also der Beginn der Dateneinheit in zyklischer Folge um jeweils eine Bytebreite, wie in FIG 1 anhand des Feldes F0 gezeigt ist. Anstelle der Subtrahierer können in analoger Weise auch Addierer verwendet werden.
[0064] FIG 4 zeigt ein zweites Ausführungsbeispiel für den Adressenumordner AD-UM in FIG 2 mit einem vierstufigen Schieberegister S-REG, das in jeder Stufe im Rang steigend eine der üblichen vier Basissadressen "0", "1", "2" und "3" gespeichert enthält. Abhängig von der Ausgangszeilenadresse Z-AD und dem Betriebsmodus MOD wird über den Auswahlschalter DEMUX die Zeilenadresse Z-AD entweder direkt allen vier ODER-Gliedern OD zugeleitet, wenn dieselbe Zeile in allen Bytespalten anzusteuern ist, oder aber es wird entsprechend dem Wert der Zeilenadresse Z-AD über die Verschiebesteuerung Z der Inhalt des Schieberegisters S-REG jeweils von der Ausgangsstellung aus zyklisch in der einen oder anderen Richtung verschoben und die Ausgänge des Schieberegisters über die Torschaltung TS freigegeben.
[0065] Ein drittes Ausführungsbeispiel für den Adressenumordner AD-UM in FIG 2 zeigt schließlich FIG 5. Gegenüber dem von FIG 4 ist das Schieberegister S-REG durch vier Auswahlschaler MUX mit jeweils vier Eingangsgruppen für die vier verschiedenen Basisadressen "0", "1", "2" und "3" ersetzt. Abhängig von der wirksamen Ausgangszeilenadresse Z-AD wird in jedem der Auswahlschalter MUX eine der vier Basisadressen zum Ausgang durchgeschaltet, wobei die Zuordnung der Basisadressen dem jeweiligen Einordnungsschema entsprechend gewählt ist.
[0066] Bei allen drei erläuterten Ausführungsformen des Adressenumordners AD-UM handelt es sich um Prinzipschaltbilder, bei denen mit Ausnahme des Betriebsartensignales MOD alle Steuerwege im vorliegenden Fall jeweils zwei Adern zur Darstellung von zweistelligen Sinärzahlen umfassen. Bei Verwendung von Dateneinheiten in Form von Doppelwörtern mit acht Byte und entsprechend acht Zeilen im Feld würden die Steuerwege aus drei Adern bestehen, die jeweils durchzuschalten sind. Das dem Feld Fn des Basisspeichers B-SP in FIG 1 zugrundegelegte Einordnungsschema arbeitet im Vergleich zu dem des Feldes F0 nach dem umgekehrten Prinzip, d.h. die im Normalbetrieb jeweils eine Dateneinheit bildenden Bytes, z.B. An0, An1, An2 und An3, sind jeweils in der Diagonale angeordnet, während die miteinander korrespondierenden Bytes, z.B. An0, Bn0, Cn0 und Dn0, jeweils in einer Ebene liegen. Es können daher die anhand von FIG 3 bis FIG 5 erläuterten Adressenumordner Ad-UM in gleieher Weise für dieses Umordnungsschema verwendet werden, nur sind die Betriebsmodussignale MOD entsprechend zu vertauschen.
[0067] Aus der Sicht des Benutzers bedeutet die Wahl zwischen den beiden Einordnungsschemen für den Basisspeicher B-SP keinen Unerschied. Beide Einordnungsschemen bewirken aber bei konstantem Zeilenadressenteil und schrittweise fortgeschaltetem Feldadressenteil der Zugriffsadresse AD die Bildung von Strings zusammengehöriger Dateneinheiten, z.B. A0i bis Ani, mit serieller Folge der einzelnen Bytes entlang der vertikalen Zugriffsrichtung für den Basisspeicher, wobei entsprechend der Anzahl der Bytes in einer Datenebene im vorliegenden Fall vier parallele Datensrings, nämlich A0i bis Ani, B0i bis Bni, C0i bis Cni und D0i bis Dni, gebildet werden können. Dies wird besonders deutlich beim Einordnungsschema für das Feld Fn in FIG 1, wenn man die erste Zeile dieses Feldes als Ausgangspunkt nimmt und dasselbe Einordnungsschema auch dem Feld F0 zugrundeliegt. Eine solche Stringbildung eröffnet verschiedene Möglichkeiten der
[0068] Einordnung von aus vielen Dateneinheiten zusammengesetzten Dateien in den Basisspeicher, nämlich die Bildung einer Datei durch einen einzigen solchen String, so daß im vorliegenden Fall vier verschiedene Dateien gleichzeitig durch die assoziative Oberfläche ASS-FL über- prüft werden können, oder aber die Verteilung einer Datei auf die parallelen Strings durch Serienschaltung der parallelen Strings in einem vorgegebenen Speicherbereich des Basisspeichers, so daß Teile der Datei parallel überprüft werden können und damit die Datei als solche schneller überprüft werden kann.
[0069] Wie die Einordnungsschemen der Felder F0 und Fn in FIG 1 erkennen lassen, ist jeweils nur für die erste Zeile eines jeden Feldes die ordnungsgemäße Bytefolge, z.B. A00, A01, A02, A03 bzw. An0, Bn0, Cn0, Dn0, eingehalten. In den übrigen Zeilen eines jeden Feldes wird jedoch davon abgewichen. Um dennoch auch für diese Zeilen im Feld die ordnungsgemäße Bytereihenfolge sicherzustellen, werden die Dateneinheiten sowohl bei der Einspeicherung als auch bei der Ausspeicherung über Umordnungseinrichtungen D-UM-EG bzw. D-UM-AG geleitet und durch eine von der Zeilenadresse Z-AD abhängige zyklische Verschiebung der jeweiligen Byteserie die jeweils benötigte Reihenfolge hergestellt.
[0070] Die Datenumordner können in ähnlicher Weise aufgebaut sein wie die Adressenumordner von FIG 4 oder besser FIG 5, jedoch mit dem Unterschied, daß an die Stelle der Basisadressen die einzuschreibenden bzw. gelesenen Bytes treten und die Steuerung durch die Betriebsart MOD entfällt. Weiterhin ist zu berücksichtigen, daß eine bei der Eingabe in der einen Richtung vorgenommene zyklische Verschiebung bei der Ausgabe durch eine in entgegengesetzter Richtung vorzunehmende Verschiebung kompensiert werden muß.
[0071] Statt mehrstufiger Multiplexer können je Subeinheit auch mehrstufige Demultiplexer mit entsprechend vielen Ausgangsgruppen verwendet und die einander jeweils entpre- chenden Ausgangsgruppen über ODER-Glieder zusammengefaßt werden.
[0072] Beim Betrieb des Basisspeichers B-SP gemäß FIG 1 werden alle Dateneinheiten vom Eingabeleitungssystem D-EG zunächst über einen Datenumordner D-UM-EG geleitet, der abhängig von der anstehenden Zeilenadresse Z-AD die benötigte Bytefolge entsprechend dem gewählten Einordnungsschema herstellt. Die so bereitgestellte Bytefolge wird dann in das angesteuerte Feld F... im Basisspeicher B-SP unter Mitwirkung des Adressenumordners AD-UM in der Adressensteuerung AD-ST eingespeichert. Beim Auslesen aus dem Basisspeicher wird die Dateneinheit ebenfalls über einen Datenumordner D-UM-AG geleitet und die benötigte Bytefolge hergestellt. Erst dann erfolgt die Weiterleitung der gelesenen Dateneinheiten, und zwar bei normalem Speicherbetrieb an das Ausgabeleitungssystem D-AG und beim assoziativen Betrieb an die assoziative Oberfläche ASS-FL, wie es durch die Ausgabewegesteuerung WS-AG, die wiederum in einfacher Weise aus zweistufigen Demultiplexern je Subeinheit zusammengesetzt sein kann, anhand des Steuersignales AG vorgegeben wird.
[0073] Anstelle von getrennten Datenumordnern für die Ein- und Ausgabe, wie in FIG 1 dargestellt, kann auch ein einziger Datenumordner D-UM vorgesehen sein, wie FIG 6 zeigt. Durch zweistufige Wegeschalter DEMUX und MUX sind dann die Datenflußwege abhängig von Steuersignalen EG/AG für die Eingabe oder die Ausgabe so umzuschalten, daß diese immer über den Datenumordner D-UM führen. Ebenso muß die Verschieberichtung des Datenumordners anhand des Ein/Ausgabesteuersignals EG/AG vorgegeben werden, damit der Datenumordner richtig arbeiten kann.
[0074] Bei einem Basisspeicher B-SP der in FIG 1 gezeigten Art können unabhängig vom normalen oder assoziativen Speicherbetrieb die gleichen Datenumordner D-UM verwendat werden. Es können aber auch getrennte Datenumordner, z.B. D-UM2, für den assoziativen Betrieb vorgesehen werden, was in FIG 6 mit dem gestrichelten Datenflußpfeil zur assoziativen Oberfläche ASS-FL am Ausgang des Basisspeichers B-SP angedeutet ist. Hierauf wird später noch eingegangen werden.
[0075] Für viele Anwendungsfälle kann die Verarbeitungsleistung des Hybrid-Assoziativspeichers merklich gesteigert werden, wenn mit der Adressensteuerung AD-ST eine Adressenmaskierung verbunden ist, so daß z.B. bei einem Suchlauf nicht der gesamte Basisspeicher in vertikaler Richtung überprüft wird, sondern nur ein ausgewählter Bereich und/oder daß in dem ausgewählten Bereich nicht jede Dateneinheitsebene, sondern in jedem Feld nur bestimmte Dateneinheitsebenen angesteuert werden. Dadurch kann der Datenfluß zur assoziativen Oberfläche ASS-FL in vielen Fällen gezielt auf die Daten beschränkt werden, die für den assoziativen Prüfvorgang benötigt werden, so daß eine Überprüfung vielfach wesentlich schneller ausgeführt werden kann.
[0076] Eine derartige Adressenmaskiersteuerung ist in FIG 7 gezeigt. Sie besteht im wesentlichen aus einem codiert arbeitenden Adressenzähler AD-Z zur Kennzeichnung eines Speicherbereiches im Basisspeicher B-SP anhand des Adressenteils AD1 und einem Maskenregister M-REG mit jeweils einer Bitstelle je Datenzeile in dem durch den Adressenteil AD1 festgelegten Speicherbereich. Die Ausgänge des Maskenregisters M-REG werden mit einer Prioritätsschaltung PRIO überwacht, die für jeden markierten Eingang nacheinander - getaktet durch einen Speicherzyklustakt T_SP - die zugehörige codierte Teiladresse AD2 liefert, die zusammen mit der Teiladresse AD1 die jeweilige Zugriffsadresse AD bildet. Entsprechend der Voreinstellung des Maskenregisters M-REG können also in dem ausgewählten Speicherbereich des Basisspeichers die einzelnen Datenzeilen in beliebiger Kombination aufeinanderfolgend angesteuert bzw. Datenzeilen in beliebiger Kombination von der Ansteuerung ausgenommen werden. Die Voreinstellung vom Adressenzähler AD-Z und dem Maskenregister M-REG erfolgt aus einem Adressenspeicher AD-SP, der bei Ansteuerung mit dem Signal lad nach Erkennung des letzten markierten Registerausganges durch die Prioritätsschaltung PRIO den jeweils nächsten Adresseneintrag in Form der Teiladresse AD1 und der Zeilenmaske Z-MASK zur Verfügung stellt.
[0077] Die Breite der Zeilenmaske Z-MASK wird zweckmäßig so gewählt, daß für den überwiegenden Teil der Anwendungsfälle ein optimales Verhältnis zwischen Speicheraufwand einerseits und Steuerungs- bzw. Zeitaufwand andererseits gegeben ist. Gegebenenfalls kann auch mit veränderbaren Feldlängen für den Adressenteil AD1 und den Maskenteil Z-MASK gerarbeitet werden.
[0078] FIG 8 zeigt die Erweiterung des Basisspeichers B-SP von FIG 1 mit einer einzigen Speichergruppe auf beispielsweise 16 Speichergruppen MD0 bis MD15, die hintereinander in Form eines dreidimensionalen Speichers oder nebeneinander in Form eines zweidimensionalen Speichers angeordnet sein können und jeweils getrennt ansteuerbar sind. Die Feld- und Zeilenauswahl erfolgt dagegen in den einzelnen Speichergruppen parallel, so daß sich - wie gezeigt - der Aufwand für den Adressenumordner AD-UM nicht erhöht. Gleiches gilt für die nicht gezeigten Datenumordner, wenn für den assoziativen Betrieb gesonderte Umordner vorgesehen werden, da beim normalen Speicherbetrieb immer nur eine Dateneinheit eingeschrieben oder gelesen wird.
[0079] Für den assoziativen Betrieb wird dagen für jede Speichergruppe ein gesonderter Datenumordner benötigt, wenn zur Steigerung der Leistungsfähigkeit des Hybrid-Assoziativspeichers jeweils eine vollständige Byteschicht oder Byteebene BS gleichzeitig zu einer entsprechend großen assoziativen Oberfläche ASS-FL durchgeschaltet wird. Der Aufwand für die Datenumordner läßt sich allerdings verringern, wenn man statt der Datenbytes erst die zugehörigen Trefferausgänge T am Ausgang der assoziativen Oberfläche ASS-FL - wie in FIG 6 angedeutet umordnet. Da jede Verknüpfungseinheit ALV ... der assoziativen Oberfläche ASS-FL nur einen Trefferausgang T aufweist, verringert sich dann der Gesamtaufwand im Vergleich zu Bytes mit je acht Bit auf ein Achtel.
[0080] Ein gemäß FIG 8 ausgebildeter Basisspeicher B-SP ist auch für ein Laden und Entladen im Streamingbetrieb besonders geeignet, wenn die Daten so aufbereitet werden, daß Dateneinheiten nacheinander in getrennte Speichergruppen eingetragen werden können. Diese Aufbereitung erfolgt durch einen vorgeschalteten Pufferspeicher.
[0081] FIG 9 zeigt eine entsprechende Prinzipschaltung. Der Einfachheit halber sind dabei für den Basisspeicher B-SP nur vier Speichergruppen MD0 bis MD3 vorgesehen und nur ein Feld Fn dargestellt, so daß sich insgesamt 16 vertikale Strings A bis P zu je 4 Byte entsprechend 16 Dateneinheiten ergeben.
[0082] Im Pufferspeicher P-SP ist je Speichergruppe MD0 bis MD3 im Basisspeicher B-SP ein EinzelSpeicher, insgesamt also die vier Einzelspeicher E-SP1 bis E-SP4 vorgesehen. Jeder Einzelspeicher E-SP ... weist eine Kapazität entsprechend der Anzahl von Strings oder Dateneinheiten je Speichergruppe MD... auf. Diese Einzelspeicher werden von der Peripherie PE aus fortlaufend nacheinander über den Auswahlschalter MUX_PE geladen, wobei die Zeilenadresse Z-AD der Einzelspeicher identisch ist mit der des Basisspeichers B-SP.
[0083] Sobald der Pufferspeicher P-SP voll ist, werden die jeweils durch dieselbe Zeilenadresse Z-AD gekennzeichneten Dateneinheiten nacheinander aus allen Einzelspeichern E-SP1 bis E-SP4 an die zugehörigen Speichergruppen MD0 bis MD3 des Basisspeichers B-SP weitergeleitet. Es sind dies also für die erste Zeile aller Einzelspeicher E-SP1 bis E-SP4 die Dateneinheiten A, E, I und M, die mit der gleichen Zeilenadreßeinstellung im Basisspeicher B-SP eingespeichert werden. Entsprechend werden bei einer Ausgabe aus dem Basisspeicher B-SP zuerst die einzelnen Dateneinheiten, z.B. A, E, I, M nacheinander über den AuswahlSchalter MUX_B__SP in die miteinander korrespondierenden Speicherabschnitte der Einzelspeicher E-SP1 bis E-SP4 eingeschrieben, und das fortschreitend von Zeile zu Zeile, bis der Pufferspeicher P-SP gefüllt ist. Bei der Weiterleitung der im Pufferspeicher P-SP gespeicherten Daten an die Peripherie PE werden dann die Einzelspeicher, z.B. E-SP1, vor der Weiterschaltung auf den jeweils folgenden Einzelspeicher, z.B. E-SP2, jeweils ganz geleert.
[0084] Anstelle von Einzelspeichern können Speicherbereiche eines einheitlichen Speichers verwendet werden. Ebenso können die einzelnen Speicherabschnitte, z.B. für die Dateneinheit A, durch eine der jeweiligen Stringlänge entsprechende Anzahl von untereinander liegenden Speicherabschnitten ersetzt werden, so daß aufeinanderfolgend zum Beispiel 16 Datenwörter AOi bis A15i als String mit 64 Byte und in gleicher Anordnung die Strings A bis P nacheinander gespeichert werden können.
[0085] Im Streamingverfahren können so ganze Feldschichten des Basisspeichers B-Sp ausgetauscht werden. Voraussetzung ist dabei nur, daß der Pufferspeicher P-SP eine der Streaminggeschwindigkeit angepaßte Arbeitsgeschwindigkeit aufweist, da der Basisspeicher B-SP langsamer als der Pufferspeicher P-SP arbeiten kann. Dabei kann es zweckmäßig sein, daß anstelle des gezeigten einen Pufferspeichers P-SP zwei Pufferspeicher vorgesehen werden, die im Wechselbetrieb arbeiten.
[0086] Kernstück der in FIG 10 gezeigten Verknüpfungseinrichtung ALV, aus der die assoziative Oberfläche eines Hybrid-Assoziativspeichers zusammengesetzt ist, ist eine einzige arithmetisch-logische Einheit ALU mit der Arbeitsbreite für ein Zeichen, in der Regel acht Bit. Den beiden Operandeneingängen der ALU ist jeweils eine Maskiereinrichtung A-MASK bzw. B-MASK, ein Operandenregister A-REG bzw. B-REG und ein Auswahlschalter A-MUX bzw. B-MUX vorgeschaltet. Über letztere können die beiden Operandenregister aus den verschiedensten Quellen wahlweise geladen werden. Im vorliegenden Falle sei unterstellt, daß dem Register B-REG in den überwiegenden Anwendungsfällen Daten aus dem Basisspeicher B-SP des Hybrid-Assoziativspeichers zugeführt werden, die anhand eines im anderen Operandenregister A-REG zur Verfügung gestellten Suchargumentes SBM zu überprüfen sind. Anstelle des Argumentes SBM können dem Register A-REG auch externe Operanden EXT-OP für durchzuführende Verknüpfungsfunktionen zugeführt werden. Des weiteren können die Operandenregister auch vom Ergebnisregister C-REG der ALU, das zweckmäßig aus einem Registersatz von z.B. 16 Einzelregistern besteht, geladen werden.
[0087] In der Regel weist das Datenleitungssystem HAS-BUS des Hybrid Asoziativspeichers eine Datenbreite auf, die einer Vielzahl von Zeichen oder Bytes entspricht, z.B. in Anpassung an die Datenleitungssysteme von Datenverarbeitunsanlagen vier oder acht Bytes. Entsprechend werden vom Basisspeicher B-SP jeweils Dateneinheiten bereitgestellt, deren Breite die Arbeitsbreite einer Verknüpfungseinheit übersteigt, und es sind dann entsprechend viele Verknüpfungseinheiten parallel mit den entsprechenden Leitungen des Datenleitungssystems HAS-BUS zu verbinden. Über das Leitungssystem HAS-BUS können aber auch Dateneinheiten dem Basisspeicher B-SP zugeführt werden, u.a. auch über die Torschaltung TS von den Ergebnisregistern C-REG der angeschlossenen Verknüpfungseinheiten.
[0088] Analog zu den beiden Operandenregistern A-REG und B-REG ist auch noch ein gesondertes Maskenregister M-REG mit vorgeschaltetem Auswahl Schalter M-MUX vorgesehen, das ebenfalls aus mehreren Quellen geladen werden kann, z.B. vom Ergebnisregister C-REG vom Datenleitungssystem HAS-BUS oder auch von einer externen Quelle.
[0089] Mit dem Maskenregister M-REG ist des weiteren eine Maskensteuerung M-ST zur Einstellung der Operandenmasken A-MASK und B-MASK gekoppelt. Neben den Maskeninformationen aus dem Maskenregister M-REG können von dieser Steuerung auch direkt zugeführte externe Maskeninformationen EXT-MASK verarbeitet und vorliegende Treffersignale T berücksichtigt werden. Die Arbeitsweise dieser Maskensteuerung M-ST wird später noch anhand von FIG 12 näher erläutert werden.
[0090] Der Ausgang der Verknüpfungseinheit ALU ist parallel mit einem Ringschieberegister S-REG und einem Quersummenbildner Q-SUM verbunden. Auf das gesonderte Schieberegister kann verzichtet werden, wenn die Operandenregister A-REG und B-REG zugleich diese Funktion übernehmen. Außerdem werden die Ergebnissignale SIG der ALU von einer Anzeigensteuerung ANZ-ST zur Bildung der üblichen Anzeigen ausgewertet. Mit dieser Anzeigensteuerung ist eine Treffersteuerung T-ST gekoppelt, die abhängig von den jeweils vorliegenden
[0091] Anzeigen und der jeweils durchgeführten Assoziationsrelation ermittelt, ob ein Treffer erzielt worden ist oder nicht und wie das jeweilige Trefferergebnis zu werten ist. Weitere Aufgaben der Treffersteuerung T-ST werden ebenfalls später noch anhand von FIG 11 erläutert werden.
[0092] Ergebnisse der Treffersteuerung T-ST können ebenso wie die Ergebnisse des Quersummenbildners Q-SUM oder der ALU bzw. des zwischengeschalteten Schieberegisters
[0093] S-REG über Auswahlschalter MUX1 und MUX2 an das Ergebnisregister C-REG weitergeleitet werden, wobei die Übernahme in das Ergebnisregister ggf. vom Vorliegen eines Steuersignals T_Ü der Treffersteuerung T-ST abhängig ist.
[0094] Das Tätigwerden der einzelnen genannten Bauteile der Verknüpfungseinheit und die Art ihres Tätigwerdens wird durch Steuersignale CMD einer übergeordneten Ablaufsteuerung festgelegt. Trotz der einheitlichen Kennzeichnung dieser Signale mit CMD dürfte klar sein, daß es sich hierbei um unterschiedliche Signale auf einer oder mehreren Signalleitungen handelt, um die einzelnen Bauteile ihrer Funktion entsprechend ansteuern zu können. Das gilt insbesondere im Hinblick auf die ALU, der mitzuteilen ist, welche Funktion jeweils ausgeführt werden soll. Insgesamt können für den Aufbau der Verknüpfungseinheit jeweils herkömmliche Bauelemente verwendet werden, wobei sich der Aufbau der Maskensteuerung M-ST und der Treffersteuerung T-ST aus der nachfolgenden Beschreibung anhand von FIG 12 und FIG 11 ergibt. Alle diese Bauelemente bzw. Bauteile werden zweckmäßig in einem integrierten Schaltkreis zusammengefaßt, um einen möglichst kompakten Aufbau mit kurzen Leitungswegen zu erhalten.
[0095] Bevor auf die Vielzahl der sich aus einem solchen Aufbau ergebenden Anwendungsmöglichkeiten eingegangen wird, soll zuvor der Aufbau der Treffersteuerung T-ST anhand von FIG 11 und der Aufbau der Maskensteuerung M-ST anhand von FIG 12 erläutert werden.
[0096] FIG 11 zeigt im linken oberen Teil die Anzeigensteuerung ANZ-ST, die in herkömmlicher Weise die benötigten Anzeigen aus den Signalen SIG der ALU ermittelt. Es sind dies beispielsweise die Anzeigen OV für den Überlauf, Z für das Ergebnis Null und VZ für das Vorzeichen des Verknüpfungsergebnisses. Aus diesen Anzeigen werden in der Einrichtung T-SIG die den einzelnen Assoziationsrelationen entsprechenden Treffersignale gebildet, von denen mit dem Auswahlschalter MUX-TA das jeweils zutreffende Treffersignal ausgewählt und als Trefferanzeige TA weitergeleitet wird. Die einzelnen Treffersignale werden beispielsweise nach der folgenden Tabelle gebildet, wobei die in der Tabelle gezeigten Verknüpfungen und Zuordnungen nur ein Ausführungsbeispiel darstellen, das in beliebiger Weise abgewandelt werden kann.
[0097]
[0098] Ist die von der jeweils durchgeführten Assoziationsrelation abhängige Verknüpfungsbedingung für die Anzeigen erfüllt, so wird auf der zugehörigen Ausgangsleitung der Einrichtung T-SIG ein Treffer mit dem Signal "1" angezeigt, während ein Nichttreffer das Signal "0" liefert.
[0099] Zwei weitere Eingänge des Auswahlschalters MUX-TA können außerdem mit den Trefferausgängen der jeweils benachbarten beiden Verknüpfungseinheiten ALV_{( n-1 )} und ALV_{(n + 1 )} verbunden sein . In gleicher Weise ist der Ausgang des Auswahl schalters MUX-TA für die T refferanzeige TA mit den entsprechenden Anschl üssen der benachbarten Verknüpfungseinrichtungen verbunden .
[0100] Damit ist auch eine T refferübernahme zur Aufrechter- haltung der Trefferkettung bei der Überprüfung von geketteten Datenteilfolgen möglich, wenn das Suchargument zwei gekettete Datenteilfolgen erfaßt.
[0101] Die so ermittelte und ausgewählte Trefferanzeige TA wird nun nicht unmittelbar als Treffer T weitergeleitet, sondern sie wird gegebenenfalls abhängig von, dem jeweiligen Anwendungsfall entsprechenden Randbedingungen modifiziert. Zu diesem Zweck ist ein aus den UND-Gliedern U1 bis U4 und den ODER-Gliedern 01 und 02 bestehendes Verknüpfungsnetzwerk vorgesehen, das Setz- und Rücksetzsignale S bzw. R für eine nachgeschaltete bistabile Kippstufe PH-FF liefert. Im vorliegenden Falle ist entsprechend der Arbeitsbreite der Verknüpfungseinheit je Bitstelle eine Kippstufe vorgesehen, insgesamt also die Kippstufen PH-FFO bis PH-FF7, von denen jeweis eine über den vorgeschalteten Auswahlschalter DEMUX-K angesteuert wird. Mit diesen Kippstufen können so in einfacher Weise bei de r Überprüfung von Datenfolgen mit einem aus mehreren Zeichen bestehenden Argument entstehende Teiltreffer gekettet und daraus bei erfüllter Kettungsbedingung ein Globaltreffer abgeleitet werden, wobei darüber hinaus eine Kettung solcher Globaltreffer von unterteilten Datenfolgen möglich ist.
[0102] Um in der Art der Modifikation und bezüglich der auszuführenden Kettungsfunktionen möglichst frei zu sein, können die Trefferkippstufen PH-FF... durch das Verknüpfungsnetzwerk V-N sowohl unbedingt als auch bedingt gesetzt oder zurückgesetzt werden, was durch die Steuersignale S und R für die unbedingte Einstellung und durch die Steuersignale S_b und R_b für die bedingte, d.h. für die von der jeweiligen Trefferanzeige TA abängige Einstellung ermöglicht wird, die wie die übrigen Signale CMD von einer übergeordneten Steuerung geliefert werden.
[0103] Die von den Kettungskippstufen PH-FF0 bis PH-FF7 zur Verfügung gestellten Treffersignale sind durch einen nachgeschalteten Auswahlschalter MUX-H wiederum einzeln auswählbar und können verschieden gewertet werden, indem z.B. ein Treffer als Nichttreffer oder aber als solcher gewertet wird. Die damit verbundene Invertierungsfunktion übernimmt das Inverterglied I. Auch kann unabhängig von dem tatsächlich erzeugten Treffersignal ein fest vorgegebenes Signal "0" oder "1" als Treffer gewertet werden. Die entsprechende Auswahl und Festlegung trifft letztendlich der AuswahlSchalter MUX-T abhängig von wirksamen Steuersignalen CMD, der das endgültige Treffersignal T liefert, das in an sich bekannter Weise der die Treffersignale der assoziativen Oberfläche überwachenden Trefferauswertesteuerung - T-AUSW z.B. in FIG 1 - zugeleitet wird. Von dem Treffersignal T kann intern auch die Übernahme des jeweiligen ALU-Ergebnisses oder der Einstellung der Kettungsflipflops PH-FFo bis PH-FF7 in das Ergebnisregister C-REG abhängig von der Einstellung des Auswahlschalters MUX2 (FIG 10) abhängig gemacht werden, was in FIG 11 durch die Pfeile T_Ü für den Übernahmetakt und C-REG für die Kippstufeneinstellung angedeutet ist.
[0104] Um mit einer derartigen Treffersteuerung auch die Bedingungen im Rahmen eines Sortiervorganges erfüllen zu können, ist die Trefferanzeige TA mit dem Ausgang des Auswahlschalters MUX-H durch das UND-Glied U6 verknüpft, dessen Ausgang an einen weiteren Eingang des Auswahlschalters MUX-T herangeführt ist. Ein ausgewähltes Trefferflipflop, z.B. PH-FFO, kann daher als Bytegrenzen-Kettungsglied verwendet werden , wenn b eispiel sweise der den UND-Gliedern U1 bis U4 zugef ührte Takt CL jeweil s nur bei Erreichen der Bytegrenze eines Sortierbitmuster-Bytes ausgel öst wird .
[0105] Die gezeigte Treffefsteuerung T-ST läßt sich in einfacher Weise auch für das Sperren der zugehörigen Verknüpfungseinheit, beispielsweise bei als aussortiert gekennzeichneten Daten, verwenden, indem bei Vorliegen eines Einzeltreffers und einem davon, z.B. durch eine übergeordnete Steuerung, abgeleiteten Steuersignal CMD über das UND-Glied U8 eine Kippstufe S-FF gesetzt wird, die das UND-Glied U7 am Ausgang des Auswahlschalters MUX-T sperrt. Die Treffersteuerung kann damit keine Treffersignale T mehr an die übergeordnete Trefferauswertesteuerung T-AUSW liefern. Darüber hinaus kann das Ausgangssignal SORT der Kippstufe S-FF unmittelbar als Sperrsignal den Maskiereinrichtungen A-MASK und B-MASK zugeführt werden, wie in FIG 10 angedeutet ist, so daß durch eine generelle Sperrung der beiden betroffenen Datenpfade durch die nachgeschaltete ALU keine Daten mehr verarbeitet werden können. Durch eine derartige Blockade einer Verknüpfungseinheit ALV wird automatisch z.B. ein in einem Hilfsspeicherbereich des Basisspeichers B-SP gespeichertes Datum im weiteren Verlauf des Sortiervorganges nicht mehr berücksichtigt und auf diese Weise als aussortiert markiert.
[0106] Selbstverständlich kann die Blockade einer Verknüpfungseinheit ALV auch auf anderem Wege erzielt werden, z.B. über die Einstellung des Maskenregisters M-REG abhängig vom Ausgangssignal des UND-Gliedes U8 der Treffersteuerung T-ST in Verbindung mit der nachgeschalteten Maskensteuerung M-ST. Eine derartige Treffersteuerung arbeitet daher weitgehend universell.
[0107] Weiter Anwendungsmöglichkeiten eröffnet darüber hinaus die vorgesehene Maskensteuerung M-ST von FIG 10, deren Aufbau sich aus FIG 12 ergibt. Entsprechend den einzelnen Bitstellen der beiden Masken A-MASK und B-MASK liefert die Maskensteuerung MST acht einzelne Steuersignale, die von den UND-Gliedern U am Ausgang der Maskensteuerung abgeleitet werden. Diese UND-Glieder U sind über ihre invertierten Eingänge durch ein Signal M-INH im Rahmen einer externen Maskeninformation EXT-MASK in der Weise steuerbar, daß die über die vorgeschalteten ODER-Glieder 0 jeweils bereitgestellten Steuersignale entweder gesperrt oder freigegeben werden, wobei das Signal "1" die Abdeckung und das Signal "0" die Freigabe der jeweils zugehörigen Bitstelle bewirkt. Abhängig vom Signal M-INH wird also die Maskierfunktion entweder unterdrückt - alle Signalleitungen führen das Signal "0" - oder durchgeführt. Beim maskierten Arbeiten, also beim Signal M-INH = 0, werden die über die ODER-glieder 0 bereitgestellten Signale weitergeleitet. Diese können wahlweise von einer extern zugeführten Bitstrukturmaske EXT-BIT oder von der im Maskenregister M-REG bereitstehenden Bitstrukturmaske abgeleitet werden. Darüber hinaus besteht durch den Auswahlschalter MUX-M abhängig von Steuersignalen CMD in Verbindung mit der Kippstufe M-FF die Möglichkeit, ein Sperrsignal M zu erzeugen, das über die ODER-Glieder 0 und die UND-Glieder U an alle Ausgangsleitungen der Maskensteuerung M-ST weitergeleitet wird und damit beide Masken A-MASK und B-MASK vollständig sperrt, so daß die bereitgestellten Operanden von der ALU nicht verarbeitet werden können. Dieses Sperrsignal kann der Reihe nach vom vorliegenden Tref- fersignal T, von einem Bit einer externen Bytemaske EXT-BYT oder von den einzelnen Bits der im Maskenregitser M-REG bereitgestellten Bitstrukturmaske abgeleitet werden. Die Maskensteuerung eröffnet damit eine Vielzahl von Möglichkeiten zur Maskierung, indem alle Verknüpfungseinheiten der assoziativen Oberfläche gleichartig oder individuell mit einer Bitstrukturmaske für das zu verarbeitende Zeichen beaufschlagt werden und/oder indem einzelne Verknüpfungseinheiten entsprechend einer von außen vorgegebenen oder einer intern abgeleiteten Bytestrukturmaske gesperrt werden.
[0108] Die Trefferauswertesteuerung T-AUSW überwacht in herkömmlicher Weise die von den einzelnen Verknüpfungseinheiten ALV der assoziatien Oberfläche ASS-FL gelieferten Treffersignale T, um einerseits die Treffersignale T der Reihe nach zu identifizieren und andererseits die Gesamtzahl der Treffer je Prüfung zu ermitteln, z.B. beim Sortieren.
[0109] Zur Identifizierung und Adressierung kann die Trefferauswertesteuerung T-AUSW analog dem Bild aus "Electronic" August 17, 1970, Seite 100 aus je einer bistabilen Kippstufe zur Zwischenspeicherung je eines der TrefferSignale, aus einem nachgeschalteten Prioritätsnetzwerk und gegebenenfalls aus einem "1 aus n"-Decoder bestehen. Zur Ermittlung der Trefferanzahl werden die Signalausgänge der bistabilen Kippstufen parallel an ein Addiernetzwerk angeschlossen, dem gegebenenfalls ein Vergleicher zur Ableitung der Summensignale 0, = 1 und > 1 nachgeschaltet ist. Eine andere Realisierung mit Zählern statt einem Addiernetzwerk zeigt FIG 5 der eingangs genannten DE-OS 32 16 905. Der bisher erläuterte Hybrid-Assoziativspeicher kann damit folgende Aufgaben erfüllen:
[0110] 1. Es können Dateneinheiten einzeln nacheinander in den Basisspeicher übernommen oder aus diesem entnommen werden, wobei Listen über die im Basisspeicher enthaltenen Dateien mit den ihnen zugeordneten Speicherbereichen geführt werden.
[0111] 2. Es können gleichzeitig alle Zeichen einer horizontalen Zeichenebene des Basisspeichers zur assoziativen Oberfläche durchgeschaltet oder in Form der Ergebnisregisterinhalte von dieser übernommen werden.
[0112] 3. Es können abhängig von in fortlaufender Folge bereitgestellten Steuerbefehlen und Parameter verschiedene assoziative Prozeduren durchgeführt werden.
[0113] 4. Die auszuführenden Prozeduren können aus vorgegebenen Befehlsfolgen zur Durchführung von Assoziationsrelationen und Verknüpfungsoperationen in gemischter Folge sowie aus trefferabhängigen Befehlen verschiedener Art bestehen.
[0114] 5. Es können in den Ergebnisregistern der Verknüpfungseinheiten in der assoziativen Oberfläche enthaltene Informationen a) in die verschiedenen Register derselben Verknüpfungseinheit für alle Verknüpfungseinheiten der assoziativen Oberfläche gleichzeitig übertragen werden, b) über das Datenleitungssystem von den Verknüpfungseinheiten jeweils einer Speichergruppe gleichzeitig ausgegeben werden oder c) für alle Verknüpfungseinheiten der assoziativen
[0115] Oberfläche gleichzeitig in eine vorgegebene horizontale Zeichenebene des Basisspeichers übernommen und aus dieser der assoziativen Oberfläche, z.B. den Maskenregistern, wieder zur Verfügung gestellt werden.
[0116] Aufgrund dieser allgemeinen Steuerungsmöglichkeiten ergibt sich eine Vielzahl von möglichen Arbeitsabläufen für die Auswertung der Treffersignale:
[0117] 1. Durch die Treffersignale T der assoziativen Oberfläche ASS-FL können die zu den angezeigten Treffern gehörigen Dateneinheiten adressiert angesteuert und aus dem Basisspeicher B-SP ausgespeichert werden.
[0118] 2. Nicht immer ist eine sofortige Übergabe der jeweils erhaltenen Treffersignale an eine übergeordnete Steuerung erwünscht. Man kann daher die Treffersignale der gesamten assoziativen Oberfläche ASS-FL zunächst in einer vorgegebenen Bytescheibe BS des Basisspeichers B-SP Zwischenspeichern. Dazu wird nach der Durchführung einer Assoziationsrelation und Zwischenspeicherung der erhaltenen Trefferanzeigen TA in einer der Kippstufen PH-FF... (FIG 11) zunächst das Operandenregister A-REG mit einem externen Operanden EXT-OP geladen, der pro Byte nur eine einzige Bitstelle mit dem Wert "1" aufweist. Außerdem wird das andere Operandenregister B-REG mit dem Zeichen 0000 0000 oder einem Trefferzeichen aus dem Sasisspeicher B-SP geladen. Beide Operanden werden in der ALU durch die Funktionen "UND" bzw. "ODER" verknüpft und das am Ausgang der ALU auftretende Ergebnismuster abhängig vom gespeicherten Treffer mit dem Signal T_Ü ins Ergebnisregister C-REG übernommen, von wo es als Trefferzeichen in den Basisspeicher B-SP übertragen wird.
[0119] Man kann so Treffer aus aufeinanderfolgenden Prozeduren aufsammeln und einer späteren Auswertung zuführen, indem jeweils dieselbe Bitstelle eines Trefferzeiehens überschrieben wird, oder aber indem den einzelnen Treffersignalen der aufeinanderfolgenden Prozeduren jeweils eine der im vorliegenden Fall zur Verfügung stehenden acht Bitstellen des Trefferzeichens zugeordnet wird.
[0120] 3. Die gebildeten Trefferzeichen werden als Masken benutzt, wobei die unmittelbar aus dem Ergebnisregister C-REG oder aus dem Basisspeicher B-SP in das Maskenregister M-REG der zugehörigen Verknüpfungseinheiten in der assoziativen Oberfläche übernommen werden, so daß für die einzelnen Verknüpfungseinheiten AVL ... individuelle Masken als Bitstruktur - oder als Bytestrukturmaske zur Verfügung stehen.
[0121] 4. Unabhängig von der unter Punkt 2) genannten Möglichkeit können bei auftretenden Treffern die Verknüpfungsergebnisse vom Ausgang der ALU unmittelbar in eines der Ergebnisregister C-REG übernommen werden.
[0122] 5. Zur Durchführung von Ähnlichkeitsbewertungen der von den Zeichen verkörperten Bitmuster mit Bewertung der einzelnen Bits des Zeichens wird mit der ALU-Funktion "GLEICH" ein Trefferrauster am Ausgang der ALU erzeugt. Die angezeigten Bit- Treffer werden durch den Quersummenbildner Q-SUM am Ausgang der ALU aufaddiert und das Ergebnis in Form einer Dualzahl in einem der Ergebnisregister C-REG zwischengespeichert. Durch zusätzlieh eingeschobene Steueroperationen kann nach jeder Ähnlichkeitsprüfung das erzielte Ergebnis zu einem im Ergebnisregister bereits vorliegenden Ergebnis vorausgegangener Ähnlichkeitsprüfungen addiert werden, so daß man die Einzelbitsummen einer ganzen Prozedur erhält, z.B. für die Ähnlichkeitsprüfung von Zeichenfolgen. Die Ergebnisse können jeweils auch in einer vorgegebenen Bytescheibe des Basisspeichers B-SP abgespeichert werden. Dies ermöglicht auch eine spätere Auswertung, z.B. die Sortierung nach dem Grad der Ähnlichkeit.
[0123] 6. Zur Gewichtung von Treffersignalen T nach einer durchgeführten Assoziationsrelation werden im Operandenregister A-REG nachfolgend bereitgestellte Gewichtsoperanden zu einem im Ergebnisregister C-REG bereits vorliegenden Ergebnis durch die ALU hinzuaddiert und das neue Gewichtungsergebnis abgespeichert, wobei die Treffer mit unterschiedlichen Gewichten bewertet werden können. Die so gebildeten Gewichtssummen können beispielsweise zur Ähnlichkeitsbewertung von Zeichenfolgen gegenüber einem Suchargument herangezogen werden. Auch in diesem Falle können die Gewichtungsergebnisse in einer vorgegebenen Bytescheibe BS des Basisspeichers B-SP abgespeichert werden.
[0124] 7. Durch die Trefferauswertesteuerung T-AUSW der assoziativen Oberfläche ASS-FL kann die Anzahl der gleichzeitig auftretenden Treffer T in Form einer Dualzahl ermittelt werden. Das ermöglicht Ähnlichkeitsbewertungen von einzelnen Bytescheiben oder Bytescheibengruppen aus dem Basisspeicher und kann für Sortiervorgänge ausgenutzt werden.
[0125] Die für die Assoziationsrelation jeweils benötigten Suchargumente können, wie bereits erläuert, aus verschiedenen Quellen im Operandenregister A-REG bereitgestellt werden. Auch die Zeichen einer Bytescheibe BS des Basisspeichers B-SP können als Suchargumente dienen, so daß diese mit einer beliebigen Anzahl anderer Bytescheiben des Basisspeichers verglichen oder verknüpft werden kann.
[0126] Insgesamt ergibt die so ausgebildete assoziative Oberfläche in Kombination mit dem speziell ausgebildeten Basisspeicher einen Hybrid-Assoziativspeicher mit bisher nicht erreichter universeller Anwendbarkeit und Leistungsfähigkeit verbunden mit fast unbegrenzter Speicherkapazität, der für die unterschiedlichsten Aufgaben geeignet ist.
[0127] Eine dieser möglichen Aufgaben besteht in einem Aufsuchen von Daten anhand eines vorgegebenen Suchargumentes aus den im Basisspeicher abgespeicherten Datenfolgen, was nachfolgend anhand von FIG 13 und FIG 15 näher erläutert werden soll.
[0128] Das Suchargument ARG möge - wie FIG 13 zeigt - aus mehreren Zeichen, z.B. A bis L, zusammengesetzt sein und in einem Parameterspeicher - PAR-SP (FIG 24) - gespeichert vorliegen. In diesem Falle ist jeweils auf Gleichheit zwischen dem jeweils gültigen Suchargumentzeichen und den aus dem Basisspeicher bereitgestellten Datenzeichen zu prüfen, was durch einen der Funktion "B-A" entsprechenden Steuerbefehl CMD der ALU (FIG 10) aller Verknüpfungseinheiten ALV... der assoziativen Oberfläche ASS-FL mitgeteilt wird.
[0129] Bevor jedoch der Suchvorgang gestartet werden kann, sind wenigstens die Startadressen für den Basisspeicher B-SP und den Parameterspeicher PAR-SP bereitzustellen. Anhand dieser Startadressen werden die beiden Speicher zu Beginn des Suchvorganges angesteuert und die jeweils ersten Zeichen der Parameter und die der gleichzeitig zu prüfenden Datenfolgen in die Register der einzelnen Verknüpfungseinheiten ALV... geladen. Dann wird der bereitgestellte Assoziationsbefehl ausgeführt und von der Trefferauswertung T-AUSW überprüft, ob für eine der Datenfolgen wenigstens ein Treffer T... vorliegt. Ist dies nicht der Fall, dann beginnt der Suchvorgang von neuem, und zwar mit dem jeweils ersten Zeichen der Parameter PAR, aber mit einer um einen Zeichenschritt gegenüber der ursprünglichen Startadresse veränderten Folgestartradresse für den Basisspeicher.
[0130] FIG 13 zeigt eine schematische Darstellung der Zuordnung für beispielsweise aus jeweils 256 Zeichen bestehenden Datenteilfolgen, von denen aber nur zwei, nämlich die Datenteilfolgen DF0 und DF1, dargestellt sind. Das Suchargument ARG besteht aus der Zeichenfolge A bis L, die in der gezeigten Weise auf die beiden Datenfolgen DF0 und DF1 verteilt in der zu überprüfenden Datenmenge enthalten und aufzusuchen ist.
[0131] Mit dem Beginn des Suchvorganges wird das erste Zeichen A des Suchargumentes ARG als Suchbitmuster SBM allen Verknüpfungseinheiten der assoziativen Oberfläche zur Verfügung gestellt, und es werden die ersten Zeichen der Datenfolgen gleichzeitig überprüft. Im vorliegend angenommenen Fall ist das Ergebnis negativ, und der Suchvorgang wird erneut gestartet, indem bei unverändertem Suchbitmuster entsprechend dem ersten Zeichen A des Suchargumentes ARG nun die zweiten Zeichen der Datenfolgen überprüft werden usw., bis beim 252. Zeichen der Datenfolgen ein Treffer erzielt wird. Demzufolge wird die Trefferkettung wirksam geschaltet, was mit einem Pfeil T-KET angedeutet ist, und anschließend mit jedem in Folge zu überprüfenden Zeichen der Datenfolgen das Suchbitmuster SBM entsprechend dem vorgegebenen Suchargument ARG in Folge geändert.
[0132] Sollte im Rahmen der weiteren Prüfung mal eine Treffermeldung für alle Datenfolgen ausbleiben, dann müßte der Suchvorgang erneut begonnen werden. Im vorliegenden Fall bricht die Trefferkettung jedoch nicht ab. Allerdings wird mit dem letzten Zeichen E der Datenfolge DF0 das Ende der Datenteilfolgen erreicht, was z.B. durch das Erreichen des Speicherendes oder der vorgegebenen Endadresse für den zu überprüfenden Speicherbereich im Basisspeicher B-SP erkannt wird. Damit wird - wie durch den Pfeil T-UM angedeutet ist - die Trefferkettung umgeschaltet und mit der ursprünglichen Startadresse für den Basisspeicher bei fortlaufender Zeichenfolge des Suchargumentes ARG der Suchvorgang fortgesetzt. Die Trefferkettung für die Datenfolge DFO wird damit entsprechend dem Datenkettungspfeil zwischen dem ersten Zeichen F der Datenfolge DF1 und dem letzten Zeichen E der Datenfolge DF0 auf die erste Datensäule umgeschaltet.
[0133] Um letzteres zu verdeutlichen, ist im oberen Teil von FIG 13 ein Teil der einzelnen Treffersteuerungen T-ST in Anlehnung an FIG 11 wiedergegeben und die Verknüpfung für die Überleitung der Trefferanzeigen TA auf die Kettungssteuerung der jeweils benachbarten Verknüpfungseinrichtung ALV angedeutet, so daß z. B. nach der Umschaltung die Trefferanzeige TA1 zum Treffersignal T0 führt, als würde die Suche in der ersten Datensäule für die Datenteilfolge DF0 fortgesetzt.
[0134] Eine andere Möglichkeit der Trefferkettung bei Erreichen des Endes der zu überprüfenden Datenteilfolgen ist in FIG 14 dargestellt, wonach die Trefferkettung in die die assoziative Oberfläche ASS-FL überwachende Trefferauswertesteuerung T-AUSW verlagert ist. Jeder Trefferleitung z.B. T0 bis T63, der assoziativen Oberfläche ist dazu eine bistabile Kippstufe zugeordnet, die analog den Trefferkippstufen PH-FF in FIG 11 über ein Verknüpfungsnetzwerk TV-N angesteuert werden und bedingt oder unbedingt abhängig von Signalen S/R_BED gesetzt werden können. Diese Kippstufen bilden zusammen ein zyklisches Schieberegister T-SREG, so daß durch Verschieben mit einem Schiebetakt K-CL um jeweils einen Schritt bei Erreichen des Endes der Datenteilfolgen im Rahmen eines Suchvorganges die in einer Kippstufe geketteten Treffer auch mit den nachfolgenden Treffern der zyklisch nachfolgenden Datenteilfolge gekettet werden können, ohne daß eine Umschaltung innerhalb der einzelnen Verknüpfungseinrichtungen ALV mit den entsprechenden Querverbindungen erforderlich ist. Dabei können ohne weiteres mehrere Datenteilfolgen von einem Suchargument erfaßt werden. Um am Ende eines dabei erfolgreich abgeschlossenen Suchvorganges den Speicheranfang für die gefundenen Daten leichter finden zu können, wird die Anzahl der Verschiebungen durch einen Zeiger KZ gezählt und gegebenenfalls in Form einer Adresse K-AD bereitgestellt.
[0135] Erreicht die Trefferkettung schließlich das Ende des Suchargumentes ARG, dann bedeudet das den erfolgreichen Abschluß des eingeleiteten Suchvorganges, was durch den Pfeil END angedeutet ist.
[0136] Im Flußdiagramm von FIG 15 wird daher immer die rechte Rücksprungschleife durchlaufen, wenn für keine der überprüften Datenfolgen ein Treffer gemeldet wird, was jeweils zum erneuten Start des Suchvorganges mit Beginn des Suchargumentes ARG bei einem verschobenen neuen Startpunkt für die Datenfolgen führt, als würde das erste Zeichen des Suchargumentes ARG Schritt für Schritt an den Datenfolgen DF ... entlang verschoben. Erst wenn aufgrund einer Treffermeldung der Startpunkt fixiert ist, wird das Suchargument Zeichen für Zeichen aufgeweitet, bis entweder die Trefferkettung abbricht oder aber das Ende des Suchargumentes erreicht wird. Dieses Aufweiten des Suchargumentes wird durch die zweite Rücksprungschleife von links in FIG 15 sichergestellt. Sollte dabei das Ende der geketteten Datenfolgen erreicht werden, dann tritt stattdessen die erste Rücksprungschleife von links in Funktion.
[0137] Eine andere sich häufig stellende Aufgabe besteht im Sortieren von Datenmengen. Das im Nachfolgenden erläuterte neue, dem Hybrid-Assoziativspeicher gemäß der Erfindung angepaßte Sortierverfahren geht auf das durch die DE-PS 23 42 660 bereits bekannte und in der europäischen Anmeldung EP-A2-0035787 fortentwickelte Sortierverfahren zurück.
[0138] Hiernach wird das jeweilige Sortierbitmuster SBM in Form eines mehrstelligen Binärzeichens zur Verfügung gestellt und bitweise abhängig von der Anzahl der bei jedem Suchlauf ermittelten Treffer und des jeweils gültigen letzten signifikanten Bits LSB entwickelt. FIG 16 zeigt den zugehörigen Sortieralgorithmus in Form einer Tabelle mit den drei Spalten "T = " für die Trefferanzahl, "LSB = " für das letzte signifikante Bit und "SBM-Änderung" für die Entwicklung des Sortierbitmusters SBM beim Vorwärts- und beim Rückwärtssortieren.
[0139] Insgesamt sind zwei Trefferfälle zu unterscheiden, nämlich mehr als ein Treffer und kein bzw. ein Treffer. Für den Fall, daß mehrere Treffer gleichzeitig vorliegen, ist das letzte signifikante Bit LSB ohne Bedeutung. In jedem Falle wird das zuletzt maßgebende Sortierbitmuster SBM durch Öffnen der Maske um eine weitere Bitstelle durch Anhängen einer 0 beim Vorwärtssortieren und durch Anhängen einer 1 beim Rückwartssortieren erweitert. Bei den übrigen Trefferfällen, kein Treffer oder ein Treffer, ist zusätzlich das letzte signifikante Bit LSB maßgebend. Ist dies eine 0, so wird diese beim Vorwärtssortieren durch Invertieren zu einer 1 oder beim Rückwärtssortieren durch Einengen der Maske einfach gestrichen. Ist das letzte signifikante Bit LSB dagegen eine 1, so wird diese beim Vorwärssortieren gestrichen oder aber beim Rückwärtssortieren durch Invertieren zu einer 0.
[0140] FIG 17 zeigt den Ablauf eines entsprechenden Sortiervorganges für drei Daten A, B und C in Form einer Tabelle mit den Spalten "SBM" für das jeweils wirksame Sortierbitmuster, "LSB" für das letzte signifikante Bit, "T" für die Trefferanzeige, "SBM-Änderung" für die vorzunehmende Änderung des Sortierbitmusters SBM und "Ausgabe" für die Ausgabe der Daten in sortierter Reihenfolge.
[0141] Zu Beginn eines Sortiervorganges liefert der Sortierbitmuster-Generator in der Regel eine Folge von binären Nullen, und alle Bitstelen bis auf die höchstwertigste werden durch die Maske abgedeckt, um so möglichst schnell zu Treffern zu kommen. Bei den als Beispiel gewählten zu sortierenden drei Daten A, B und C führt ein derartiges Sortierbitmuster zu einer Mehrfachtrefferanzeige. Das Sortierbitmuster ist daher durch Anhängen einer 0 zu erweitern. Bei der nächsten Überprüfung wird gleichfalls ein Mehrfachtreffer angezeigt und durch Öffnen der Maske eine weitere 0 angehängt. Die dritte Prüfung zeigt einen einzigen Treffer an, und zwar für den Eintrag A, der ausgegeben werden kann. Nachfolgend wird die 0 an letzter Stelle invertiert und damit in eine 1 abgeändert, so daß bei der nächsten Prüfung wiederum ein Treffer erzielt wird und diesmal der Eintrag B ausgegeben werden kann. Da das letzte signifikante Bit LSB eine 1 war, wird durch Einengen der Maske eine Stelle wieder gestrichen. Die darauffolgende Prüfung ergibt keinen Treffer, und das letzte signifikante Bit wird in eine 1 abgewandelt. Da auch die nachfolgende Überprüfung keinen Treffer ergibt, wird wiederum durch Einengen der Maske das letzte wirksame Bit gestrichen, so daß das wirksame Sortierbitmuster SBM aus einer einzigen 0 an der höchsten Stelle besteht. Auch dabei führt die Prüfung zu keinem Treffer, wenn ale bereits aussortierten Daten als solche gekennzeichnet sind, so daß diese 0 zu einer 1 invertiert wird, was dann zu einem Treffer für den letzten Eintrag C führt.
[0142] Das gezeige Beispiel behandelt einen sehr einfach ablaufenden Sortiervorgang, bei das Sortierbitmuster SBM nur einmal über mehrere Bitstellen ausgeweitet und dann wieder eingeengt wird. In der Praxis ist dagegen mit einem ständigen Wechsel zwischen Erweiterung und Einengung des Sortierbitmusters SBM in unterschiedlichem Ausmaß zu rechnen .
[0143] Das Ablaufdiagramm von FIG 18A bis 18C zeigt den Ablauf eines Sortiervorgangs entsprechend dem Verfahren gemäß der Erfindung bei vertikal gespeicherten Zeichenfolgen eines Datums. Im Kopf der FIG 18A ist oberhalb des eigentlichen Ablaufdiagramms das Sortierbitmusterfeld SBM für drei Byte 1 bis 3 dargestellt, wobei der Einfachheit halber jeweils vier Bit ein Byte bilden. Vollständige, durch eine Bytegrenze, z.B. BG1 und BG2, getrennte Bytes sind gesondert abgespeichert, und jeweils nur das an die letzte gültige Bytegrenze, z.B. 3G1, anschließende zum Teil unvollständig Byte BYTE 2 bestimmt den Fortgang des Sortiervorganges.
[0144] Das Ablaufdiagramm gliedert sich in sechs Spalten, nämlich eine für die Kennzeichnung der Auswahlläufe AWL zum Aufsuchen eines durch einen Einzeltreffer gekennzeichneten Datums, eine für die Suchläufe SL zum Aufspüren von Treffern, eine für das verwendete Suchbitmuster SBM, eine für Zeicheneinzeltreffer T_E und eine für die gesamte Trefferanzahl T_GES je Such- oder Auswahllauf SL oder AWL.
[0145] Im ersten Suchlauf SL1 besteht das Sortierbitmuster aus einer 0 in der höchstwertigsten Bitstelle und bei der Überprüfung der jeweils ersten Zeichen aller Daten ergeben sich mehrere Treffer. Das gleiche gilt für die Suchläufe 2 bis 4. Am Ende des Suchlaufes SL4 muß daher die Bytegrenze BG1 des Sortierbitmusters SBM überschritten werden. Das Byte BYTE 1 ist damit vollständig und muß zwischengespeichert werden, während das zweite Byte BYTE 2 als neues aktuelles Byte weiterzuentwickeln ist. Bevor aber eine Prüfung anhand des aktuellen Bytes des Sortierbitmusters SBM und dem zugehörigen zweiten Zeichen aller Daten durchgeführt werden kannn, muß jeweils das erste Zeichen eines jeden Datums mit dem abgespeicherten ersten Byte des Sortierbitmusters überprüft werden, und nur wenn dabei ein Treffer erzielt wird, ist eine anschließende Prüfung des zweiten Zeichens desselben Datums mit dem aktuellen Byte des Sortierbitmusters sinnvoll, da nur dann eine Übereinstimmung mit dem gesamten bisher entwickelten Sortierbitmustr SBM gegeben sein kann. Im fünften Suchlauf SL5 ist daher dieser Ablauf für jedes in der Spalte DAT verzeichnete Datum 1 bis n der Datei angegeben. Für die Daten DAT1 und 5 ist diese Voraussetzung erfüllt. Am Ende des Suchlaufes SL5 ergibt sich daher eine Mehrfachtrefferanzeige. Das aktuelle Byte des Sortierbitmusters SBM ist also mit einer weiteren 0 auf die zweite Stelle im zweiten Byte BYTE 2 zu erweitern und bestimmt den Suchlauf SL6, der im übrigen in gleicher Weise wie der Suchlauf SL5 abläuft. Am Ende wird ein Einzeltreffer angezeigt, so daß mit unverändertem Sortierbitmuster in einem ersten Auswahllauf AWL1 das auszusortierende Datum DAT 1 ermittelt und als erstes ausgegeben werden kann, was am rechten Rand des Ablaufdiagramms in FIG 18A mit AUS1 gekennzeichnet ist.
[0146] In analoger Weise wird nun das Sortierverfahren wie angegeben fortgeführt, was im Ablaufdiagramm nur bis einschließlich des fünften Auswahllaufes AWL5 dargestellt ist.
[0147] Das gewählte Beispiel von FIG 18A bis 18C beschränkt sich lediglich auf die Überschreitung einer Bytegrenze SG1 des Sortierbitmusters SBM. Jedoch dürfte klar sein, daß bei einer noch stärkeren Ausweitung des Sortierbit- musters über mehrere Bytegrenzen hinweg bei jedem Suchund Auswahllauf für jedes Datum alle abgespeicherten vollständigen Bytes des Sortierbitmusters SBM zur Prüfung vor Prüfung mit dem jeweils aktuellen Byte des Sortierbitmusters herangezogen werden müssen, um zu ermitteln, ob die erforderliche Kettungsbedingung bis zur dem aktuellen Byte vorausgehenden Bytegrenze erfüllt ist. Mit zunehmender Ausweitung des Sortierbitmusters über eine Byteweite hinaus, steigt also die Anzahl der zusätzlichen Prüfungen je Suchlauf entsprechend an, und die Suchläufe erfordern zunehmend mehr Zeitaufwand, da für jede Prüfung ein Lesevorgang im Basisspeicher erforderlich ist.
[0148] Dieser Zeitaufwand läßt sich nun auf verschiedene Arten verringern :
[0149] Eine dieser Maßnahmen besteht im sofortigen Abbruch des jeweiligen Suchlaufes, wenn ein zweiter Treffer anfällt, denn dann ergibt sich eine Mehrfachtrefferanzeige und es wird sowieso ein neuer Suchlauf mit erweitertem Sortierbitmuster erforderlich. Im Ablaufdiagramm von FIG 18A bis 18C ist das durch die Sprungpfeile AB am rechten Rand des Ablaufdiagramms angedeutet.
[0150] Eine andere Maßnahme besteht darin, statt eines Abbruches des Suchlaufes nach einem zweiten Treffer die während eines Suchlaufes durch Treffer gekennzeichneten Daten zu markieren oder die Adressen dieser Daten in einem gesonderten Speicher festzuhalten. Dadurch werden in einem Suchlauf jeweils alle relevanten Daten erfaßt und in den nachfolgenden Suchläufen brauchen nur noch diese Daten berücksichtigt zu werden. Unnötige Prüfungen entfallen dadurch, jedoch müssen auch im ersten Falle alle Daten im Basisspeicher angesteuert werden. Im anderen Falle können die Daten anhand der zwischen- gespeicherten Adressen jeweils direkt aufgesucht werden.
[0151] In gleicher Weise wie die Adressenzwischenspeicherung wirkt auch ein gesonderter Hilfsspeicher, der zweckmäßig als Teil des Basisspeichers in diesen integriert ist und damit die vorhandene assoziative Oberfläche nutzen kann, wenn alle während eines Suchlaufes durch Treffer gekennzeichneten Daten in diesen Hilfsspeicher übernommen und anschließend aus diesem heraus endsortiert werden.
[0152] Da für diesen Hilfsspeicher in der Regel nur eine begrenzte Speicherkapazität vorgesehen werden kann, die einer vorgegebenen höchsten Trefferanzahl während eines Suchlaufes entspricht, wird in einem oder mehreren Suchlaufen zunächst ein Sortierbitmuster ermittelt, das eine den Hilfsspeicher günstig füllende Anzahl von Treffern bewirkt. Erst dann werden in einem anschließenden gesonderten Übernahmel.auf mit unverändertem Sortierbitmuster die durch Treffer gekennzeichneten Daten in den HilfsSpeicher übernommen. Eine Überfüllung des Hilfsspeichers ist auf diese Weise trotz der beschränkten Speicherkapazität von vornherein ausgeschlossen.
[0153] Unabhängig von all diesen Maßnahmen zur Verminderung des Zeitaufwandes für einen Sortiervorgang lassen sich die zusätzlichen Prüfungen zur Feststellung der Kettungsbedingung für jedes Datum der zu überprüfenden Datei grundsätzlich zu einem großen Teil vermeiden, wenn für jedes Datum ein zusätzliches Kettungselement aufgewandt wird, das bei Ausweitung des Sortierbitmusters über eine Byteweite hinaus eine Aussage über die Einhaltung oder Nichteinhaltung der Kettungsbedingung bis zur jeweils gültigen Bytegrenze des Sortierbitmusters ermöglicht, auf die daher ohne zusätzliche Prüfung zurückgegriffen werden kann. Das in FIG 19A und 19B in Anlehnung an das von FIG 18A bis 18C dargestellte Ablaufdiagramm zeigt den bereits erläuterten Sortierablauf unter Berücksichtigung von individuellen Kettungsgliedern, die in einer zusätzliehen Spalte "KG" berücksichtigt sind. Außerdem ist das Ablaufdiagramm durch eine weitere Spalte "T_K" ergänzt, in der der aus der Koinzidenz von Einzeltreffer T_E und erfüllter Kettungsbedingung KG = 1 resultierende Treffer T_K vermerkt ist, der anstelle des Einzeltreffers T_E zu werten ist.
[0154] In allen dargestellten Suchläufen SL5 bis 14 und den Auswahlläufen AWL1 bis 5 entfallen daher die zusätzlichen Prüfungen für die Ermittlung der Kettungsbedingung gegenüber dem Ablaufdiagramm von FIG 18A bis 18C bei der Erweiterung des Sortierbitmusters. Der Sortiervorgang wird dadurch grundsätzlich beschleunigt, wie auch die Gegenüberstellung beider Ablaufdiagramme zeigt.
[0155] Das Ausmaß der Zeitaufwandsminderung ist auch in diesem Falle von einigen Randbedingungen abhängig: So behält z.B. die Kettungsaussage in den individuellen Kettungselementen KG nur dann ihre Gültigkeit, solange nicht eine Bytegrenze in Rückwärtsrichtung im Rahmen einer Einengung des Sortierbitmusters überschritten wird. Dies sei anhand von FIG 20 verdeutlicht, die drei verschiedene Daten DAT1 bis DAT3 einer Datei zeigt. Jedes Datum besteht jeweils aus vier Zeichen mit den eingezeichneten Sytegrenzen BG1, BG2 und BG3. Alle drei Zeichen stimmen bis zur zweiten Bytegrenze BG2 überein. Außerdem stimmen die Daten DAT2 und DAT3 bis zur Bytegrenze BG3 überein. Wird die Sytegrenze BG3 im Rahmen einer Erweiterung des Sortierbitmusers überschritten, dann ist eine positive Kettungsaussage nur noch für das Datum DAT1 gegeben. Wird anschließend das Sortierbitmuster wieder eingeengt und die Bytegrenze BG3 unterschritten, dann sind die Daten DAT2 und DAT3 wieder in den laufenden Sortiervorgang einzubeziehen. Eine gültige Kettungsaussage bezüglich der Bytegrenze BG2 besteht aber für diese Daten nicht mehr, sie ist daher neu zu ermitteln.
[0156] Bei jeder Unterschreitung einer Bytegrenze des Sortierbitmusters muß also trotz der individuellen Kettungselemente die Kettungsbedingung immer wieder neu ermittelt werden. Die zur Ermittlung der jeweils gültigen Kettungsbedingungen erforderlichen Prüfungen lassen sich also mit individuellen Kettungselementen nicht ganz umgehen. Der Zeitaufwand hierfür ist jedoch je nach Art der gewählten Kettungselemente und der Art der Kettungsaussage unterschiedlich.
[0157] Bei einer 1-BitAussage, wie sie z.B. eine bistabile Kippstufe vermittelt, kann man nicht umhin, nach der Bytegrenzenunterschreitung wie bei dem anhand von FIG 18A bis 18C gezeigten Verfahrensablauf zunächst alle nicht aussortierten Daten der Datei anhand der zwischengespeicherten Bytes des Sortierbitmusters zeichenweise bis zur neuen gültigen niedrigeren Bytegrenze zu prüfen.
[0158] Bei einer komplexeren Aussage, die z.B. die die gültige Kettungsgrenze darstellende Bytegrenze des Sortierbitmusters unabhängig vom Grad der Ausweitung des Sortierbitmusters konkret angibt und einen mehrstelligen Speicherabschnitt, z.B. in Form eines Registers oder eines Zählers, erfordert, ist je Datum nur ein Prüfvorgang in Form eines Vergleichs unabhängig von der Anzahl der gespeicherten vollständigen Bytes des Sortierbitmusters erforderlich. Stimmt nämlich die durch die Kettungsaussage bezeichnete Bytegrenze mit der unterschrittenen Bytegrenze überein, dann bestand die Kettungsbedingung bis zu dieser Bytegrenze und die Kettungsaussage ist der neuen niedrigeren Bytegrenze anzupassen, etwa durch Verringerung einer entsprechenden Kennzahl um eine 1. Ist bei dem Vergleich keine Gleichheit gegeben, dann war zwar die Kettung bis zur unterschrittenen Bytegrenze nicht gegeben, aber eine bis zur neuen niedrigeren Bytegrenze bestandene Kettung lebt bei einer entsprechenden Kettungsaussage wieder auf.
[0159] Da bei einer solchen komplexen Kettungsaussage kein unmittelbares Steuersignal für die Verknüpfung mit dem jeweils erzielten Treffersignal T_E gegeben ist, muß das Kettungssignal KG nachgebildet werden, indem z.B gleichzeitig mit der Prüfung des jeweiligen Datenzeichens mit dem aktuellen Byte des Sortierbitmusters ein Vergleich der individuellen Kettungsaussage mit der gültigen Kettungsaussage durchgeführt wird und das gewonnene Ergebnissignal als Kettungssignal KG verwendet wird. Die dazu benötigten Vergleichsaussagen können - wie noch gezeigt werden wird - in einfacher Weise von den Adressenregistern abgeleitet und von einer den Sortiervorgang überwachenden Steuerung bereitgestellt werden.
[0160] Im übrigen gelten für das anhand von FIG 19A und 19B erläuterte Sortierverfahren mit individuellen Kettungselementen die im übrigen zu dem Ablaufdiagramm von
[0161] FIG 18A bis -18C gegebenen Hinweise bezüglich Abbruch eines Suchlaufs bei auftretendem zweiten Treffer oder stattdessen Markierung der in einem Suchlauf durch Treffer gefundenen Daten bzw. bezüglich der Verwendung eines Hilfsspeichers, was in FIG 19A und 19B am rechten Rand des Ablaufdiagramms in gleicher Weise durch die zusätzlichen Vermerke angedeutet ist.
[0162] Die Durchführung dieser Sortierverfahren erfordert teilweise eine Ergänzung des bisher beschriebenen HybridAssoziativspeichers. FIG 21 zeigt ein entsprechendes Prinzipschaltbild mit einem auf eine einzige Zeichensäule beschränkten Speicher- und Auswerteteil mit den aus jeweils mehreren Zeichen, z.B. A1 bis An, bestehenden Daten A bis X einer Datei in vertikaler Ausrichtung untereinander, wobei der Einfachheit halber die versetzte Verteilung der einzelnen Zeichen auf mehrere Zeichensäulen äußer Acht gelassen ist.
[0163] Die wesentlichste Ergänzung besteht in einem gemeinsamen, durch die DE-S 23 42 660 bekannten Sortierbitmustergenerator SBM-GEN mit Maske SBM-MASK, der das jeweils aktuelle Byte des Sortierbitmusters SBM bereitstellt, das zur Verknüpfungseinheit ALV geführt wird. Außerdem ist ein zusätzlicher Speicher SBM-SP mit Schreib- und Lesesteuerung S/L-ST vorgesehen, in dem die höherwertigen vollständigen Bytes des Sortierbitmusters zwischengespeichert werden, die bei Bedarf dem Sortierbitmustergenerator SBM-GEN wieder zur Verfügung gestellt werden.
[0164] Für die Ein- und Ausgabesteuerung des Sortierbitmusterspeicher SBM-SP sind vorzugsweise zwei Adressenregister vorgesehen, nämlich REG-A für die Bereitstellung der Ausgabeadresse AD-A sowie REG-E für die Bereitstellung der Eingabeadresse AD-E, die jeweils auf zwei verschiedene Speicherabschitte des Sortierbitmusterspeichers SBM-SP hinweisen, nämlich auf den für das zuletzt eingespeicherte vollständige Byte und den für das nachfolgende, mit Überschreiten der nächsten Bytegrenze dann nicht mehr akuteile Byte aus dem Sor- tierbitmustergenerator SBM-GEN, die durch zusätzliche Takte CL_L bzw. CL_S freigegeben werden. Auf diese Weise können die Inhalte dieser Register zugleich als Bezugswerte bei Verwendung von individuellen Kettungselementen mit Angaben der zuständigen Bytegrenze benutzt und einer Kettungssteuerung KG-ST zur Verfügung gestellt werden, wie noch gezeigt werden wird.
[0165] Der aus den Flußdiagrammen von FIG 18A bis C bzw. FIG 19A und 19B ersichtliche Arbeitsablauf beim Sortieren dieser im Basisspeicher B-SP enthaltenen Datenmenge wird durch eine gemeinsame Steuerung SORT-ST sichergestellt, die daher mit der Trefferauswertesteuerung T-AUSW gekoppelt ist und die jeweils benötigten SteuerSignale liefert.
[0166] Je Datum oder auch Datenzeichen ist außerdem ein gesondertes Kennungsbit SB vorgesehen, das z.B. im gesetzten Zustand die bereis erfolgte Aussortierung anzeigt und entweder über die Verknüpfungseinheit ALV oder direkt an die Steuerung SORT-ST geleitet wird, um eine Umsteuerung auf das nachfolgende Datum zu bewirken. Diese Kennungsbit SB werden in an sich bekannter Weise beim Aussortieren eines Datums auf Veranlassung der Steuerung SORT-ST gesetzt, was aber nicht näher gezeigt ist.
[0167] Wie in FIG 6 des weiteren gestrichelt angedeutet ist, kann entweder ein zusätzlicher Speicher T-AD-SP für die Zwischenspeicherung der Adressen der während eines Suchlaufes durch -Treffer gekennzeichneten Daten oder aber ein als Hilfsspeicher arbeitender zusätzlicher Teilbereich H-SP im Basisspeicher B-SP für die Zwischenspeicherung der während eines Suchlaufes durch Treffer gekennzeichneten Daten vorgesehen sein, was bereits in Verbindung mit FIG 18A bis 18C und FIG 19A und 19C erläutert worden ist.
[0168] Für die Auswahl der einzelnen Speicherabschnitte im Hilfsspeicher H-SP ist zweckmäßig eine gesonderte Adressensteuerung AD-ST2 vorgesehen. Außerdem ist im Übernahmepfad zwischen der Verknüpfungseinheit ALV und dem Hilfsspeicherbereich H-SP ein nicht gezeigter Pufferspeicher erforderlich, da in der Regel eine der beiden Adressensteuerungen wirksam und entweder nur geschrieben oder nur gelesen werden kann.
[0169] Zwischen jeder Verknüpfungseinheit ALV und der gemeinsamen Trefferauswertesteuerung T-AUSW kann bei Verwendüng individueller Kettungselemente je Datum eine zusätzliche Kettungssteuerung KG-ST in Ergänzung der in den Verknüpfungseinheiten ALU bereis vorgesehenen Kettungssteuerungen (FIG 11) angeordnet sein, die mit der gemeinsamen Steuerung SORT-ST ebenfalls eng zusammenarbeiten.
[0170] Für das durch das Ablaufdiagramm der FIG 18A bis C bestimmte Verfahren sind derartige Kettungssteuerungen KG-ST jedoch nicht erforderlich, da die benötigten Kettungen von der Treffersteuerung T-ST (FIG 11) der Verknüpfungseinheit ALV übernommen werden können. Da jedoch in Form einer der Kippstufen PH-FF in den Verknüpfungseinheiten je Säule bei den einzelnen Sachläufen durch die relevanten Datenblockbereiche des Basisspeiches B-SP nur ein Kettungselement zur Verfügung steht, muß nach Überschreiten der ersten Bytegrenze BG1 des Sortierbitmusters SBM die Kettungsbedingung jeweils erst neu hergestellt werden.
[0171] Die Trefferübernahme in das Kettungselement PH-FF ab- hängig von einem lediglich bei Erreichen einer Bytegrenze ausgelösten Takt stellt jedoch ein Problem: Ist das letzte Bit vor der erreichten Bytegrenze eine "0", dann kann erst am Ende des Suchlaufs festgestellt werden, ob die Bytegrenze tatsächlich überschritten wird, nämlich bei einem Mehrfachtreffer, oder ob das letzte Bit in eine "1" abzuwandeln ist und damit die Bytegrenze noch nicht überschritten wird. Führt die 0 an letzter Stelle zu einem Rücksetzen der Kippstufe und würde danach die Bytegrenze nicht überschritten, dann wäre die Kettungsaussage fälschlich geändert worden. Diese Schwierigkeit wird umgangen, wenn auch nach Ausbleiben einer Bytegrenzenüberschreitung die Kettungsbedingung in einem gesonderten Durchlauf neu ermittelt wird.
[0172] Die Bytegrenzenkettung kann aber auch in die zusätzliche Kettensteuerung KG-ST verlagert werden, deren Aufbau FIG 22 bzw. FIG 23 zeigt.
[0173] Seim Ausführungsbeispiel nach FIG 22 dient in Anlehnung an die Treffersteuerung der Verknüpfungseinheiten eine bistabile Kippstufe FF71 als Kettungselement, das abhängig vom Treffersignal T_E der Verknüpfungseinheit ALV über UND-Glieder U71 und U72 in Verbindung mit einem Übernahmetakt CL-S/R bei jeder Prüfung gesetzt oder rückgesetzt wird. Dieser ersten Kippstufe ist eine zweite Kippstufe FF72, beispielsweise ein D-Flipflop, nachgeschaltet, das mit einem aus der Koindenz der Zustände "Bytegrenze erreicht" und "Mehrfachtreffer vorhanden" abgeleiteten Signal CL-ÜB getaktet wird und den in der Kippstufe FF71 zunächst nur zwischengespeicherten Kettungszustand endgültig übernimmt. Ist die Kippstufe FF72 gesetzt und damit die Kettungsbedingung bis zur gültigen Bytegrenze erfüllt, dann wird bei jedem nachfolgenden durch das aktuelle Byte des Sortierbitmusters ausgelösten Treffer T_E das UND-G lied U73 auf gesteuert , und das
[0174] Treffersignal führt über den nach Überschreiten der ersten Bytegrenze mit CMD entsprechend eingestellten Auswahlschaler MUX70 zum geketteten Treffersignal T_K. Ist dagegen die erste Bytegrenze noch nicht überschritten, wird das Einzeltreffersignal T_E über den Auswahlschalter MUX70 direkt weitergeleitet. Durch die zusätzliche Kippstufe FF72 entfällt in diesem Falle der gesonderte Suchlauf beim Ausbleiben einer erwarteten Bytegrenzenüberschreitung. Anstelle der Schaltungskombination mit den UND-Gliedern U71 und U72 sowie der Kipstufe FF71 als S/R-Flipflop kann auch eine Schaltungskombination mit einem D-Flipflop verwendet werden.
[0175] Der bisher beschriebene Teil der Kettungssteuerung KG-ST erfordert zur Herstellung der Kettungsbedingung ebenfalls das vorherige Überprüfen aller betroffenen Zeichen eines Datums anhand der zwischengespeicherten Bytes des Sortierbitmusters, was in Verbindung mit dem anhand von FIG 18A bis C erläuterten Verfahrensablauf bereits angesprochen worden ist.
[0176] Die vorherige Prüfung aller Zeichen kann jedoch gemäß dem Ablaufdiagramm von FIG 19A und 19B entfallen, wenn die innerhalb der Vielfachanschlüsse V vorgesehenen Bauteile in Verbindung mit dem zusätzlichen gestrichelt eingezeichneten ODER-Glied OD70 vielfach, und zwar idividuell für jedes Datum der Datei, vorgesehen sind, wobei die Auswahl durch die gestrichelte, adressenbedingte Auswahlleitung AD_x parallel zur Auswähl des zugehörigen Datums im Basisspeicher B-SP erfolgt.
[0177] Wie bereits in Verbindung mit FIG 20 erläutert, muß jedoch bei jeder Bytegrenzenunterschreitung die Ket- tungsbedingung für alle Kettungselemente erst neu ermittelt werden, was dann Zeichen für Zeichen durchgeführt werden kann.
[0178] Der Aufwand hierfür läßt sich jedoch wesentlich verringern, wenn gemäß dem Ausführungsbeispiel von FIG 23 in der Kettungssteuerung KG-ST als individuelles Kettungselement eine Speichereinheit, z.B. eines besonderen Kettungsspeichers K-SP, vorgesehen wird die beispielsweise die Nummer BG-NR der die gültige Kettungsgrenze darstellenden Bytegrenze des Sortierbitmusters SBM gespeichert enthält.
[0179] Mit einer Teiladresse AD_x wird bei jeder Prüfung eines Datenzeichens aus dem Basisspeicher B-SP die zugehörige Speichereinheit im Kettungsspeicher K-SP angesteuert, und die darin enthaltene Kettungsangabe BG-NR einem Vergleicher VG zugeführt und mit der im Adressenregister REG-A enthaltenen Adresse AD-A für das letzte zwischengespeicherte vollständige Byte des Sortierbitmusters SBM verglichen. Bei Übereinstimmung liefert der Vergleicher VG ein die Gültigkeit der Kettung anzeigendes Signal KG, das durch das UND-Glied U81 mit dem zugehörigen Treffersignal T_E verknüpft wird und wie bei der Anordnung nach FIG 22 das gekettete Treffersignal T_K liefert.
[0180] Wird eine Bytegrenze überschritten, was ebenfalls mit einem aus der Koinzidenz der Zustände "Bytegrenze erreicht" und "Mehrfachtreffer vorhanden" abgeleiteten Signal CL-ÜB angezeigt wird, dann sind alle Daten der zu prüfenden Datei in einem eingeschobenen Änderungslauf auf das Vorliegen der Kettungsbedingung bei unverändertem aktuellen Byte des Sortierbitmusters SBM zu überprüfen und der zugehörige Kettungseintrag BG-NR im Kettungsspeicher K-SP gegebenenfalls zu ändern, z.B. durch Erhöhen um eine 1 bei Zählung der überschrittenen Bytegrenzen.
[0181] Dazu wird zweckmäßig ein zentraler Bytezeiger SBM-BZ in der Sortiersteuerung SORT-ST verwendet, dessen Anzeige normalerweise mit dem Inhalt des Adressenregisters REG-A übereinstimmt und um eine Einheit verringert oder erhöht werden kann.
[0182] Bei einer Bytegrenzenüberschreitung wird zunächst die im Register RE-A als Vergleichswert enthaltene Adresse AD-A beibehalten und der Bytezeiger SBM-BZ um eine Einheit erhöht, um die neue gültige Bytegrenze zu kennzeichnen. Ergibt die Überprüfung ein positives gekettetes Treffersignal T_K, dann wird das UND-Glied U82 aufgesteuert und der neue Kettungseintrag mit dem am Ausgang des ODER-Gliedes OD80 wirksam werdenden Schreibbefehl CL-SP vom Bytezeiger SBM-BZ übernommen. Erst am Ende ds Änderungslaufes und nach Abspeicherung des vollständigen aktuellen Bytes des Sortierbitmusters SBM im Speicher SSM-SP wird dann auch mit dem Takt CL-S der Inhalt des Registers REG-A an den Inhalt des Zeigers SBM-BZ angepaßt und über ein Plus-1-Netzwerk +1 der Inhalt des Registers REG-E zur Kennzeichnung des Speicherplatzes für das neue aktuelle Byte des Sortierbitmusters SBM entsprechend geändert, bevor der eingeleitete Sortiervorgang fortgesetzt wird.
[0183] Bei jeder Unterschreitung einer Bytegrenze, die durch das Signal CL-UN der Sortiersteuerung SORT-ST angezeigt wird, lassen sich die neuen Kettungsbedingungen viel leichter als bei der Anordnung vo FIG 22 ermitteln, da nur die Kettungseinträge BG-NR in den einzelnen Speicherabschnitten des Kettungsspeichers K-SP der Kettungssteuerung KG-ST zu überprüfen sind. Als nächstes wird in diesem Fall der Zeiger SBM-BZ um eine Einheit erniedrigt, ohne den Inhalt des Registers REG-A zunächst zu ändern. Dann werden die einzelnen Einträge BG-NR im Kettungsspeicher K-SP nacheinander angesteuert, und wieder mit der im Register REG-A enthaltenen Vergleichsangabe AD-A verglichen. Bei Übereinstimmung steuert das Signal KG des Vergleichers VG das UND-Glied U83 auf und veranlaßt über das ODERGlied OD80 mit dem Signal CL-SP die Übernahme des Zeigerstandes als neuen Kettungseintrag in das jeweils angesteuerte Kettungselement im Kettungsspeicher K-SP. Besteht keine Übereinstimmung, bleibt der vorliegende Kettungseintrag unverändert, da dann keine gültige Kettung bis zur unterschrittenen Bytegrenze bestanden hat.
[0184] Nach Überprüfung aller Kettungseinträge im Kettungsspeicher K-SP wird dann mit der noch unveränderten Adesse AD-A im Register REG-A das letzte abgespeicherte Byte des Sortierbitmusters SBM dem Sortierbitmustergenerator SBM-GEN aus dem Speicher SBM-SP zur Verfügung gestellt, und erst anschließend werden die Inhalte der Register REG-A und REG-E dem neuen Stand des Zeigers SBM-BZ mit dem Takt CL-S angepaßt und der Sortiervorgang fortgesetzt.
[0185] Bei den bisher erläuterten Sortierverfahren wurde vorausgesetzt, daß gemäß der DE-PS 23 42 660 die für das Sortierbitmuster nicht relevanten Bitstellen im Rahmen der für die Ausführung von Assoziationsfunktionen vorhandenen Arbeitsbreite der Verknüpfungseinheit von z.B. acht Bit je Zeichen durch eine in gleicher Weise wie das Sortierbitmuster in der Breite sich ändernde Maske, z.B. SSM-MASK in FIG 6, von der jeweiligen Prüfung ausgeschaltet werden, so daß sich die Prüfung jeweils nur auf die vom Sortierbitmuster belegten Bitstellen beschränkt, und daß außerdem mit der Assoziationsfunktion "GLEICH" auf Gleichheit geprüft wird.
[0186] Dieses Ausschalten der nicht relevanten Bitstellen durch eine Maskeneinstellung kann jedoch entfallen, wenn man statt der Assoziationsfunktion "GLEICH" die Assoziationsfunktion "KLEINER/GLEICH" bzw. GROESSER/GLEICH" verwendet, die nicht relevanten Bitstellen beim Sortierbitmuster alle auf "1" bzw. auf "0" setzt und die volle, nicht maskierte Arbeitsbreite der Verknüpfungseinheit für die Prüfung verwendet.
[0187] Gegeben sei beispielsweise das folgende Sortierbitmuster
[0188] 0 1 0 1 0 | X X X X wobei mit X die nicht relevanten Bitstellen bezeichnet sind. Bei der Prüfung auf Gleichheit ergeben sich Treffer, die im Bereich zwischen den beiden folgenden Werten liegen:
[0189] 0 1 0 1 0 | 0 0 0 0 und 0 1 0 1 0 | 1 1 1 1
[0190] Will man beispielsweise von der niedrigsten Rangfolge an Daten im Rang steigend also in Aufwärts- oder Vorwärtsrichtung, sortieren, dann kommt man zu demselben Ergebnis, wenn man die nicht relevanten Bitstellen alle auf "1" setzt und statt der Relation "GLEICHHEIT" die Relation "KLEINER/GLEICH" prüft. Analoges gilt für das Sortieren in umgekehrter Richtung, also in Abwärts- oder Rückwärtsrichtung, wobei jedoch alle nicht relevanten Bitstellen auf "0" zu setzen sind und die Relation "GROESSER/GLEICH" überprüft wird.
[0191] Dies bedeutet insbesondere bei Verwendung einer univer- seil arbeitenden Verknüpfungseinrichtung für die Ausführung der Assoziationsfunktionen, wie sie beispielsweise anhand von FIG 10 beschrieben ist, keine Schwierigkeiten, vermeidet aber die sonst erforderliche Ausblendung der nicht relevanten Bitstellen bei der Prüfung, ohne daß das Sortierverfahren im übrigen dadurch beeinflußt wird.
[0192] Unabhängig von der Art der Prüfung läßt sich das Verfahren auch in einfacher Weise dadurch nutzen, aus einer Datenmenge von Daten mit verschiedenem Wert oder Rang das Datum mit dem höchsten oder niedrigsen Wert auszusuchen. Wird das Datum mit dem niedrigsten Wert gesucht, dann wird ein Sortiervorgang in Vorwärtsrichtung beginnend it dem Sortierbitmuster "00...00" durchgeführt, bis ein erster Sortiertreffer erzielt wird. Wird das Datum mit dem höchsten Wert gesucht, dann erfolgt der Sortiervorgang in Rückwärtsrichtung, beginnend mit dem Sortierbitmuster "11...11".
[0193] Bricht man dabei den Sortiervorgang nicht bereits nach dem ersten Sortiertreffer ab, sondern erst nach einer vorgegebenen Anzahl m von Sortiertreffern, dann erhält man zwangsläufig m Daten mit den m niedrigsten bzw. den m höchsten Werten, und zwar in geordneter Reihenfolge.
[0194] Auch ein Aufsuchen von Daten mit Werten, die einem vorgegebenen Bezugswert am nächsten liegen, ist mit dem Sortierverefahren gemäß der Erfindung in einfacher Weise möglich.
[0195] Werden dabei Daten gesucht, deren Werte entweder nur kleiner oder nur größer sind als der Bezugswert, dann werden in einem Ausscheidungslauf zunächst alle Daten der zu prüfenden Datenmenge mit dem Bezugswert als Sortierbitmuster überprüft und die Daten als aussortiert markiert, deren Werte größer bzw. kleiner als der Bezugswert sind. Will man den oder die am nächsten liegenden kleineren Werte erfassen, so erfolgt die Ausscheidung mit der Assoziationsfunktion "GROESSER ALS", im anderen Falle mit "KLEINER ALS". Für die danach verbleibenden Daten wird dann ein Sortiervorgang durchgeführt, wobei Ausgangspunkt für das Sortierbitmuster gleichfalls der vorgegebene Bezugswert ist. Bei der Suche nach kleineren Werten erfolgt die Sortierung in Abwärts- oder Rückwärtsrichtung, im anderen Falle in Aufwärts- oder Vorwärtsrichtung. Auch hierbei kann dar Sortiervorgang jeweils nach dem ersten Sortiertreffer bereits abgebrochen werden, wenn nur das nächstliegende Datum gewünscht wird, oder aber erst nach m erzielten Sortiertreffern, wenn die m nächstliegenden Daten gesucht werden.
[0196] Sollen dagegen Daten mit dem nächstliegenden Wert bzw. Werten unabhängig von der Richtung gesucht werden, so bietet sich in Verbindung mit einem Hilfsspeicher die Möglichkeit an, zwei Sortierläufe der vorbeschriebenen Art zur Ermittlung von Datens sowohl mit kleinerem als auch mit größerem Wert durchzuführen, die dabei gefundenen Daten in den Hilfsspeicher zu übernehmen und durch schrittweises Ändern des Sortierbitmusters abwechselnd in die eine und in die andere Richtung mit dem Bezugswert als Ausgangs-Sortierbitmuster zu prüfen, bis der erste oder die ersten m Sortiertreffer erzielt sind.
[0197] FIG 24 zeigt schließlich den Gesamtaufbau eines HybridAssoziativspeichers für große Datenmengen mit den im vorangehenden bereits im einzelnen erläuterten Bauteilen, wobei der Sortierbitmustergenerator SBM-GEN zu- sammen mit der Maske und dem Speicher für die vollständigen Sortierbitmuster-Bytes (FIG 21) der Einfachheit halber als eine Einheit dargestellt ist und auf die gesonderte Darstellung der Adressenumordner und Datenumordner in Verbindung mit dem ßasisspeicher B-SP verzichtet wurde.
[0198] Der Basisspeicher B-SP ist in Anlehnung an FIG 8 dreidimensional aus mehreren Speichergruppen MDO bis MD15 mit je vier Zeichensäulen aufgebaut, die jeweils durch individuelle Datenwege mit der zugehörigen Verknüpfungseinheit ALV der assoziativen Oberfläche ASS-FL verbunden sind, was durch die senkrecht stehenden Pfeile des Leitungssystems HAS-BUS angedeutet ist, so daß 64 Datenzeichen in Form einer Zeichen- oder Byteebene BS gleichzeitig in der einen oder anderen Richtung ausgetauscht werden können. Die Datenleitungen jeweils aller Zeichensäulen einer Speichergruppe, z.B. MDO, können außerdem parallel auf einen entsprechend breiten Datenweg - angedeutet durch den waagerechten Pfeil mit Schalter S des Leitungssystems HAS-BUS - geschaltet werden, so daß jeweils vier Zeichen als eine Dateneinheit bei normalem Speicherbetrieb mit der nicht dargestellten Peripherie ausgetauscht werden können. Mit diesem breiten Datenweg ist auch ein Pufferspeicher P-SP gekoppelt, z.B. der in FIG 9 dargestellte.
[0199] In den Basisspeicher B-SP ist auch ein Hilfsspeicher H-SP integriert, der aus den übrigen Teilen des Basisspeichers aussortierte Daten für die Endsortierung übernimmt und dessen Speicherkapazität je vertikaler Zeichensäule dem Umfang des größten Datums eines Dateieintrages entspricht, das für die Sortierung maßgebend ist. Es können also die Daten von 64 verschiedenen vorsortierten Dateieinträgen parallel überprüft und endsortiert werden. Zur Übernahme von im Rahmen eines Suchlaufes durch Treffer gekennzeichneter Daten aus dem Basisspeicher B-SP in den Hilfsspeicherbereich H-SP wird das jeweils gelesene Datum aus einem Datenblock, z.B. DB2, zunächst in einen an das Leitungssystem HAS-BUS angeschlossenen Pufferspeicher B-SP übernommen und anschließend in Zuordnung zu jeweils einem freien Säulenbereich in den Hilfsspeicher H-SP eingeschrieben. Unabängig von der Lage des einzelnen Datums innerhalb der einzelnen Zeichensäulen 0 bis 63 werden dabei immer freie Säulenbereiche im Hilfsspeicherbereich H-SP aufgefüllt. Die Zuordnung des jeweils freien Säulenbereiches erfolgt durch einen selbständigen Teil der Adressensteuerung AD-ST. Bei derartigen Umspeicherungen, werden wie auch im Verkehr mit dem Leitungssystem HAS-BUS, im vorliegenden Fall immer vier zu einer Dateneinheit zusammengefaßte Datenzeichen gleichzeitig transportiert.
[0200] Für die Parameter PAR, die für die Bearbeitung der Daten durch die assoziative Oberfläche ASS-FL benötigt werden, ist ein gesonderter Parameterspeicher PAR-SP vorgesehen, der in gleicher Weise wie der Basisspeicher B-SP aufgebaut und organisiert ist, allerdings mit dem Unterschied, daß infolge der gleichartigen Beaufschlagung aller Verknüpfungseinheiten ALV... der assoziativen Oberfläche mit einheitlichen Parametern lediglich eine Speichergruppe mit jeweils einer Zeichensäule je Parameterart, z.B. Suchargumentzeichen, Bitstrukturmaske, externer Operand, Gewichtungsfaktor, benötigt wird. Mit einer einheitlichen Speicheradresse wird dadurch bei jeder Ansteuerung immer die jeweils benötigte Gruppe von Parametern in Form einer Dateneinheit bereitgestellt.
[0201] Die für die Bereitstellung der Parameter PAR und die Ansteuerung der Daten im Basisspeicher B-SP benötigten Speicherbefehle und -adressen CMD-SP sowie die jeweils benötigten Steuerbefehle CMD-ST werden beispielsweise von einer übergeordneten Steuerung HAS-ST geliefert, in die auch die Steuerung SORT-ST von FIG 21 integriert ist und die entsprechend den erläuterten Verfahren arbeitet.
[0202] Die für den Hybrid-Assoziativspeicher gemäß der Erfindüng benötigten Bauteile lassen sich in einfacher dem Fachmann geläufiger Weise aus handelsüblichen Bauelementen aufbauen: So kann der Basisspeicher B-SP beispielsweise aus Speicherelementen HYB 4164-2 des Anmelders zusammengesetzt sein, die 64 000 1-Bit-Einheiten -aufweisen, wobei wenigstens neun Speicherelemente, parallel geschaltet, 64 000 verfügbare einzeln ansteuerbare Speichereinheiten mit jeweils acht Datenbits und einem Sortierbit liefern.
[0203] Die arithmetisch-logische Einheit ALU kann beispielsweise aus dem Baustein SN 74S 181 und SN 74S 182 der Firma Texas Instruments aufgebaut sein.
[0204] Analoges gilt für die übrigen benötigten Bauteile, für die beispielsweise folgende Bauelemente der Fa. Texas Instruments verwendet werden können:
[0205] Übrige Speicher: SN 74S 189 mit 16 x 4 Bit
[0206] Binärzähler: SN 74 163 mit 4 Binärstellen Demultiplexer: SN 74 156, SN 74 138, SN 74 154
[0207] Multiplexer: SN 74 157, SN 74 153, SN 74 151
[0208] Addierer: SN 74 82 und SN 8483
[0209] Priority encoder: SN 74 148 oder SN 74 147
[0210] Um jeweils Bauteile mit der gewünschten Anzahl von Ein- und Ausgängen zu erhalten, sind diese Bauelemente jeweils in der benötigten Form miteinander zu kombinieren.

权利要求:
ClaimsPatentansprüche
1. Hybrid-Assoziativspeicher, g e k e n n z e i c h n e t - durch einen nichtassoziativen Basisspeicher (B-SP) zur Speicherung wenigstens einer Gruppe von Dateneinheiten in einzeln auswählbaren Dateneinheitsabschnitten mit Unterteilung jeder Dateneinheit (z.B. A0i) in eine konstante Anzahl (z.B. 4) von Subeinheiten (z.B. Byte A00 bis A03), mit Speicherung der Dateneinheiten derselben Gruppe in Form von vertikalen Säulen unter Bildung von jeweils durch eine Feldadresse (z.B. F-AD0) ansteuerbaren Feldern (z.B. F0), wobei jeweils eine der Anzahl (4) von Subeinheiten innerhalb einer Dateneinheit entsprechende Anzahl von Dateneinheitsabschnitten ein Feld (z.B. F0) bilden, und mit versetzter Speicherung der jeweils miteinander korrespondierenden Subeinheiten (z.B. A00, B00, C00 und D00) der ein Feld (z.B. F0) bildenden Dateneinheiten (z.B. A0i bis D0i) in jeweils verschiedenen Subeinheitsabschnitten der verschiedenen Dateneinheitsabschnitte, - durch Lese- und Schreibeinrichtungen in Verbindung mit Adressiereinrichtungen (AD-ST) zur Ableitung der jeweiligen Feldadresse (z.B. F-AD0) und der für den jeweiligen Subeinheitsabschnitt benötigten Ansteueradresse (z.B. Z-AD_BSP0) aus der jeweils vorgegebenen Adresse (Z-AD) für einen der Dateneinheitsabschnitte im jeweiligen Feld (z.B. F0) und mit Einrichtungen zur Wahl des Betriebsmodus (MOD) und zur Einstellung der Adressiereinrichtung (AD-ST) zwecks gleichzeitiger Auswahl jeweils der eine Dateneinheit (z.B. A0i) bildenden Subeinheiten (z.B. A00, A01, A02 und A03) beim normalen Speicherbetrieb oder jeweils der miteinander korrespondierenden Subeinheiten (z.B. A00, B00, C00 und D00) aller Dateneinheiten (z.B. A0i bis D0i) eines Feldes (z.B. F0) und mit Umordnungseinrichtungen (D-UM...) zur Änderung der Reihenfolge der Subeinheiten innerhalb der jeweils zu speichernden bzw. zu lesenden Dateneinheit wenigstens bei normalem Speicherbetrieb zwecks Wiederherstellung der ordnungsgemäßen Reihenfolge beim Lesen bzw. zwecks Herstellung der für das Einordnen im Speicher erforderlichen Reihenfolge abhängig von der jeweils maßgeblichen Adresse (Z-AD) für einen der
Dateneinheitsabschnitte im jeweiligen Feld (z.B. F0) und - durch eine assoziative Oberfläche (ASS-FL) mit einer der Anzahl der gleichzeitig im Basisspeicher (B-SP) auslesbaren Subeinheiten entsprechenden Anzahl von Verknüpfungseinheiten (ALV...) zur gleichzeitigen assoziativen Überprüfung der aus dem Basisspeicher zugeführten einzelnen Subeinheiten und mit einer für alle Verknüpfungseinheiten (ALV...) gemeinsamen Trefferauswertesteuerung (T-AUS).
2. Hybrid-Assoziativspeicher nach Anspruch 1, g e k e n n z e i c h n e t durch Adressiereinrichtungen (AD-ST) und Umordnungseinrichtungen (D-UM...), durch die beim normalen Speicherbetrieb die jeweils eine Dateneinheit (z.B. A0i) bildenden Subeinheiten (A00, A01, A02 und A03) alle in dem durch die vorgegebene Adresse (Z-AD) gekennzeichneten Speicherabschnitt eines Feldes (F0) und die korrespondierenden Subeinheiten (z.B. A00, B00, B00 und D00) jeder Dateneinheit (z.B. A0i, B0i, C0i und D0i) dieses Feldes (F0) von Dateneinheitsabschnitt zu Dateneinheitsabschnitt um jeweils einen Subeinheitsabschnitt zyklisch versetzt gespeichert werden.
3. Hybrid-Assoziativspeicher nach Anspruch 1, g e k e n n z e i ch n e t durch Adressiereinrichtungen (AD-ST) und Umordnungseinrichtungen (AD-UM, D-UM...), durch die beim normalen Speicherbetrieb jeweils die miteinander korrespondierenden Subeinheiten (z.B AnO, BnO, Cno und Dno) aller Dateneinheiten (Ani, Bni, Cni, Dni) eines Feldes (z.B. Fn) alle in den h die vorgegebene Adresse (Z-AD) gekennzeichneten Dateneinheitsabschnitt und die einzelnen Subeinheiten (An0, An1, An2 und An3) jeder Dateneinheit von Dateneinheitsabschnitt zu Dateneinheitsabschnitt um einen Subeinheitsabschnitt zyklisch versetzt gespeichert werden.
4. Hybrid-Assoziativspeicher nach einem der Ansprüche 1 bis 3, g e k e n n z e i c h n e t durch einen von der Adresse (Z-AD) zur Kennzeichnung eines Dateneinheitsabschnittes innerhalb eines vorgegebenen Feldes (z.b. F0) steuerbaren Adressenumordner (AD-UM) innerhalb der Adressiereinrichtung (AD-ST) zur Steuerung der vertikalen Versetzung im Feld (F0) bei der Auswahl der einzelnen Subeinheitsabschnitte, der als Adressengenerator für jede Spalte (z.B. BSP0 bis BSP3) der Subeinheitsabschnitte im Sasisspeicher eine gesonderte Ansteueradresse (z.B. Z-AD_(BSP)) zur Auswahl jeweils eines Subeinheitsabschnittes in der zugehörigen Spalte liefert, so daß zur gleichzeitigen Auswahl der jeweils eine gewünschte Dateneinheit bildenden Subeinheitsabschnitte wie bei einem herkömmliehen Speicher lediglich die Adresse (Z-AD) zur Kennzeichnung des gewünschten Dateneinheitsabschnittes innerhalb des zuständigen Feldes erforderlich ist.
5. Hybrid-Assoziativspeicher nach Anspruch 4, g e g e k e n n z e i c h n e t , durch eine mit dem Adressenumordner (AD-UM) gekoppelte Umschalteeinrichtung zur Änderung des Betriebsmodus (MOD), so daß abhängig vom jeweiligen Betriebsmodus und dem gewählten Einordnungsschema für die einzelnen Dataneinheiten im Feld entweder eine für alle Spalten einheitliche Ansteueradresse (z.B. Z-AD_(BSP0)) zυr Auswahl von Subeinheiten desselben Dateneinheitsabschnittes oder aber für alle Spalten unterschiedliche Ansteueradressen (Z-AD_(BSP0) bis Z-AD7_(BSP3)) zur Auswahl von vertikal versetzten Subeinheiten aus verschiedenen Dateneinheitsabschnitten bereitgestellt werden.
6. Hybrid-Assoziativspeicher nach einem der Ansprüche
1 bis 5, g e k e n n z e i c h n e t durch eine einzige Umordnungseinriehtung (D-UM) für die Änderung der Reihenfolge der Subeinheiten innerhalb einer jeweils zu lesenden oder zu speichernden Dateneinheit und durch Umschalter (MUX/DEMUX) zur Steuerung des Datenflußweges über die Umordnungseinriehtung (D-UM) abhängig von der Richtung des Datenflusses bei der Eingabe (EG) oder bei der Ausgabe (AG).
7. Hybrid-Assoziativspeicher nach einem der Ansprüche
1 bis 6, g e k e n n z e i c h n e t durch getrennte Umordnungseinrichtungen für den Datenfluß beim normalen und assoziativen Speicherbetrieb.
8. Hybrid-Assoziativspeicher nach Anspruch 7, g e k e n n z e i c h n e t durch eine Umordnungseinrichtung für den assoziativen Speicherbetrieb an den Ergebnisausgängen der Verknüpfungseinheiten (z.B. ALV1 bis ALV4) der assoziativen Oberfläche (ASS-FL), so daß erst die Verknüpfungsergebnisse in die richtige Reihenfolge gebracht werden.
9. Hybrid-Assoziativspeicher nach einem der Ansprüche 1 bis 6, g e k e n n z e i c h n e t durch eine gemeinsame Umordnungseinriehtung (D-UM) für den normalen und den assoziativen Speicherbetrieb.
10. Hybrid-Assoziativspeicher nach einem der Ansprüche 6 bis 9, g e k e n n z e i c h n e t durch Datenumordnungseinrichtungen (D-UM), bestehend aus einer der Anzahl (z.B. 4) von Subeinheiten je Dateneinheit entsprechenden Anzahl von Verteilerschaltern mit einer der Anzahl von Subeinheiten entsprechenden Anzahl von Ausgangsgruppan zur Weiterleitung der am Eingang anstehenden Subeinheiten bzw. Verknüpfungsergebnisse an die jeweils durch die Adresse (Z-AD) für den gewünschten Dateneinheitsabschnitt gekennzeichnete Ausgangsgruppe und bestehend aus ODER-Gliedern zur Zusammenfassung der miteinander korrespondierenden Ausgangsgruppen der einzelnen Verteilerschalter.
11. Hybrid-Assoziativspeicher nach einem der Ansprüche 1 bis 10, g e k e n n z e i c h n e t durch eine mit den Adressiereinrichtungen (AD-ST) gekoppelte Maskiersteuerung (AD-MASK) zur Festlegung der bei assoziativen Suchvorgängen nacheinander anzusteuernden Dateneinheiten in der jeweils gewünschten Kombination.
12. Hybrid-Assoziativspeicher nach Anspruch 11, bei dem die Maskiersteuerung (AD-MASK) besteht
- aus einem voreinstellbaren Adressenzähler (AD-Z) zur Kennzeichnung des Beginns eines ausgewählten Speicherbereichs im Basisspeicher (B-SP),
- aus einem den ausgewählten Basisspeicherbereich überwachenden voreinstellbaren Maskenregister (M-REG) mit einer Bitstelle je Dateneinheitsabschnitt, - aus einer Prioritätsschaltung (PRIO) zur Überwachung der Ausgänge des Maskenregisters (M-REG) und zur Erzeugung von entsprechenden Teiladressen (AD2) in fortlaufender Folge mit einem Speicherzyklustakt (T_SP), die zusammen mit der vom Adressenzähler (AD-Z) bereitgestellten Teiladresse (AD1) die jeweilige Ansteueradresse (AD) für den Basisspeicher (B-SP) bildet und - aus Einrichtungen zur Erzeugung eines Ladesignales (Lad) für die Nachladung des Adressenzählers (AD-Z) und des Maskenregisters (M-REG) aus einem Adressenspeicher (AD-SP) nach Überprüfung jeweils aller Ausgänge des Maskenregisters (M-REG) durch die Prioritätsschaltung (PRIO).
13. Hybrid-Assoziativspeicher nach einem der Ansprüche 1 bis 12 mit einem Basisspeicher (B-SP), bestehend aus mehreren, jeweils eine Gruppe von Dateneinheiten in jeweils gleichartiger Anordnung aufnehmenden Speichergruppen (z.B. MD0 bis MD15) mit Adressiereinrichtungen (MD-AD) zur wahlweisen Auswahl jeweils nur einer der Speichergruppen (z.B. MD0) und zur gleichzeitigen Auswahl aller Speichergruppen bei Schreiben oder Lesen von Dateneinheiten, abhängig vom Betriebsmodus (MOD) in Verbindung mit einer einheitlichen Adressierung der Felder und Subeinheitsabschnitte in den einzelnen Speichergruppen (MDO bis MD15) durch einen gemeinsamen Adressenumordner (AD-UM), so daß beim normalen Speicherbetrieb Dateneinheiten einzeln nacheinander eingespeichert oder gelesen werden können, während beim assoziativen Speicherbetrieb durch gleichzeitige AnSteuerung aller Speichergruppen (MD0 bis MD15) jeweils eine entsprechende Anzahl von Dateneinheiten gleichzeitig zur assoziativen Oberfläche (ASS-FL) durchschaltbar ist.
14. Hybrid-Assoziativspeicher nach Anspruch 7 oder 8 in Verbindung mit Anspruch 13 und einem der Ansprüche 10 bis 12, g e k e n n z e i c h n e t durch gesonderte, parallel arbeitende Umordner für die Dateneinheiten je Speichergruppe (z.B. MD0 bis MD15) zur Abwicklung des assoziativen Speicherbetriebes und einen gemeinsamen Umordner (D-UM) für die Dateneinheiten aller Speichergruppen zur Abwicklung des normalen Speicherbetriebes.
15. Hybrid-Assoziativspeicher nach Anspruch 13 oder 14 g e k e n n z e i c h n e t durch einen Pufferspeicher (P-SP)
- mit einer der Anzahl (z.B. 4) von Speichergruppen (z.B. MD0 bis MD3) im Basisspeicher (B-SP) entsprechenden Anzahl von Einzelspeichern (z.B. ESP1 bis E-SP4) mit fester Zuordnung zu den Speichergruppen (MD0 bis MD3) zum Laden und Entladen des Basisspeichers (B-SP), wobei jeder Einzelspeicher (z.B. E-SP1) eine der Anzahl der ein Feld (z.B. F_n) bildenden
Dateneinheiten entsprechende Anzahl von Speicherabschnitten aufweist,
- mit Auswahleinrichtungen (MUX_B-SP) zur aufeinanderfolgenden Ansteuerung der Einzelspeicher (E-SP1 bis E-SP4) im Verkehr mit dem Basisspeicher (B-SP) abhängig von der Adresse (MD-AD) der jeweils betroffenen Speichergruppe (z.B. MD0),
- mit Auswahleinrichtungen (MUX_PE) zur aufeinanderfolgenden Ansteuerung der Einzelspeicher (E-SP1 bis E-SP4) im Verkehr mit einer die Dateneinheiten nacheinander liefernden oder aufnehmenden Datenquelle (PE) und
- mit gemeinsamen Auswahleinrichtungen (Z-AD) für die Ansteuerung der einzelnen Dateneinheitsabschnitte in den Einzelspeichern (E-SP1 bis E-SP4) in Überein- Stimmung mit der Adresse (Z-AD) für den zugehörigen Dateneinheitsabschnitt im vorgegebenen Feld des Basisspeichers (B-SP), wobei im Verkehr mit der äußeren Datenquelle (PE) die Einzelspeicher jeweils vor der Umschaltung auf den nächstfolgenden vollständig geladen oder entladen werden, während im Verkehr mit dem Basisspeicher jeweils bei gleicher Adresseneinstellung die in den Einzelspeichern (E-SP1 bis ESP4) einander entsprechenden Dateneinheiten (z.B. A, E, I, M) einzeln nacheinander der jeweils zugehörigen Speichergruppe (MD...) des Basisspeichers zugeführt werden bzw. jeweils nacheinander aus den einzelnen Speichergruppen (MD0 bis MD3) ausgelesen und nacheinander in die zugehörigen Einzelspeieher (E-SP1 bis E-SP4) eingeschrieben werden, so daß bei einem Datentransfer zwischen Basisspeicher (B-SP) und dem Pufferspeicher (P-SP) jeweils die Dateneinheiten für eine vollständige Feldebene (F_n) des Basisspeichers (B-SP) in einem Zuge austauschbar sind.
16 . Hybrid-Assoziativspeicher nach Anspruch 15 , g e k e n n z e i c h n e t durch zwei im Wechse l betrieb arbeitende Pufferspeicher .
17. Hybrid-Assoziativspeicher nach einem der Ansprüche 1 bis 16, bei dem die Verknüpfungseinheiten (ALV...) der assoziativen Oberfläche (ASS-FL) bestehen
- aus jeweils einer einzigen arithmetisch-logischen Einheit (ALU) mit zwei Operandenregistern (A-REG, B-REG) und wenigstens einem Ergebnisregister (C-REG) zur Durchführung sowohl von Assoziationsrelationen als auch von Verknüpfungsfunktionen,
- aus einer mit der arithmetisch-logischen Einheit (ALU gekoppelten Auswerteeinrichtung (ANZ-ST) zur Ableitung von Anzeigen (z.B. OV, Z, VZ) aus den jeweiligen Ergebnissignalen und einer Auswerteeinrichtung (T-ST) zur Erzeugung eines Treffersignales (T) durch Korrelation der jeweils gewünschten Assoziationsrelation mit den Anzeigen,
- aus jeweils zwischen Operandeneingang der arrithmetisch-logischen Einheit (ALU) und zugehörigem Operandenregister (A-REG bzw. B-REG) angeordneten steuerbaren Maskiereinrichtungen (A-MASK bzw. B-MASK) und - aus steuerbaren Auswahlschaltern (A-MUX, B-MUX) zur Verbindung der Operandenregister (A-REG, B-REG) mit den jeweils benötigten Datenquellen (z.B. B-SP, B-REG).
18. Hybrid-Assoziativspeicher nach Anspruch 17, g ek e n n z e i c h n e t durch Einrichtungen (T-SIG) zur Erzeugung von den möglichen Assoziationsrelationen entsprechenden Steuersignalen aus den jeweils zur Verfügung gestellten Anzeigen (z.B. OV, Z, VZ) und Einrichtungen (MUX-TA) zur Auswahl jeweils eines der Steuersignale als Einzeltreffersignal (TA) abhängig von der jeweils auszuführenden Assoziationsrelation.
19. Hybrid-Assoziativspeicher nach Anspruch 17 oder 18, bei dem die Auswerteeinrichtung (T-ST) zur Erzeugung eines Treffersignales Einrichtungen zur Kettung von Einzeltreffersignalen (TA) von mehreren aufeinanderfolgenden oder teilweise aufeinanderfolgend durchgeführten Assoziationsrelationen bei der Überprüfung von Datenfolgen und zur Erzeugung von Globaltreffersignalen bei erfüllter Kettungsbedingung aufweist.
20. Hybrid-Assoziativspeicher nach Anspruch 19, g e k e n n z e i c h n e t durch den Einrichtungen zur Trefferkettung vorgeschaltete Auswahleinrichtungen (MUX-TA) für die Übernahme von Einzeltreffersignalen (TA) benachbarter Verknüpfungseinheiten (ALV_(n-1) bzw. ALV_(n+1)), so daß Treffersignale (TA-ALV_(n±1)) zwecks Kettung der Prüfungsergebnisse von geketteten Datenteilfolgen am Ende der Datenteilfolge übernommen werden können.
21. Hybrid-Assoziativspeicher nach Anspruch 19 oder 20, bei dem die Einrichtungen zur Kettung von Einzeltreffersignalen (TA) wenigstens eine bistabile Kippstufe (z.B. PH-FF0) und Einrichtungen (V-N) zum unbedingten als auch bedingten, von Einzeltreffersignalen (TA) abhängigen Setzen und Rücksetzen der Kippstufe in Verbindung mit entsprechenden Steuersignalen (S, R, S_b, R_b) aufweist.
22. Hybrid-Assoziativspeicher nach Anspruch 21, bei dem die Einrichtungen zur Kettung von Einzeltreffersignalen (TA) eine der Arbeitsbreite (z.B. 8 Bit) der Verknüpfungseinheit (ALV...) entsprechende Anzahl von bistabilen Kippstufen (z.B. PH-FFO bis PH-FF7), eine Auswahleinrichtung (DEMUX-K) für die Ansteuerung jeweils einer dieser Kippstufen abhängig von einem Steuersignal (CMD) und eine Auswahleinrichtung (MUX-H) zur Durchschaltung der Signalausgänge jeweils einer der Kippstufen (z.B. PH-FF0) auf einen gemeinsamen Ausgang (J) aufweisen.
23. Hybrid-Assoziativspeicher nach Anspruch 22, g e k e n n z e i c h n e t durch einen an die Ausgänge der Kippstufen (z.B. PH-FF0 bis PH-FF7 angeschlossenen Schalter (MU2) zur Weiterleitung der gespeicherten Treffersignale an das Ergebnisregister (C-REG) der Verknüpfungseinheit (ALV...).
24. Hybrid-Assoziativspeicher nach einem der Ansprüche 17 bis 23, g e k e n n z e i c h n e t durch einen an den Ausgang der arithmetisch-logischen Einheit (ALU) angeschlossenen Schalter (MUX2) zur Weiterleitung des jeweiligen Ergebnisses der Einheit an das Ergebnisregister (C-REG) abhängig vom Vorliegen eines Treffersignales (T).
25. Hybrid-Assoziativspeicher nach einem der Ansprüche 17 bis 23, g e k e n n z e i c h n e t durch einen an den Ausgang der arithmetisch-logischen Einheit (ALU) angeschlossene Einrichtung (Q-SUM) zur Bildung der Quersumme aus dem Ergebnis der Einheit und einen an den Ausgang des Quersummenbildners (Q-SUM) angeschlossenen Schalter (MUX2) zur Weiterleitung des Ergebnisses an das Ergebnisregister (C-REG) abhängig vom Vorliegen eines Treffersignales (T).
26. Hybrid-Assoziativspeicher nach einem der Ansprüche 17 bis 25, g e k e n n z e i c h n e t durch eine zwischen dem Ausgang und den Eingängen der arithmetischlogischen Einheit (ALU) vorgesehene Einrichtung (S-REG) zur zyklischen Verschiebung der Bitstellen innerhalb eines weiterzuleitenden Ergebnisses der Einheit.
27. Hybrid-Assoziativspeicher nach Anspruch 25 und 26, bei dem die Einrichtung (S-REG) zur zyklischen Verschiebung aus einem Ringschieberegister besteht, das am Ausgang der arithmetisch-logischen Einheit (ALU) angeschlossen ist und bei dem die Ausgänge sowohl des Ringschieberegisters (S-REG) als auch des Quersummenbildners (Q-SUM) wahlweise über einen Schalter (MUX2) mit dem Ergebnisregister (C-REG) verbindbar sind.
28. Hybrid-Assoziativspeicher nach Anspruch 26, bei dem die Operandenregister (A-REG, S-REG) der Verknüpfungseinheiten (ALV...) als Schieberegister ausgebildet sind.
29. Hybrid-Assoziativspeicher nach einem der Ansprüche 17 bis 28, bei dem die Verknüpfungseinheiten (ALV...) neben den beiden Operandenregistern (A-REG, B-REG) ein Maskenregister (M-REG) mit vorgeschaltetem AuswahlSchalter (M-MUX) für die Zuführung von Maskeninformationen von verschiedenen Datenquellen (z.B. B-SP, C-REG) für die interne Steuerung der Maskiereinrichtungen (A-MASK, B-MASK) aufweist.
30. Hybrid-Assoziativispeicher nach Anspruch 29, g e k e n n z e i c h n e t durch eine gesonderte Maskensteuerung (M-ST), durch die die beiden Maskiereinrichtungen (A-MASK, B-MASK) wahlweise für ein unmaskiertes oder maskiertes Arbeiten einheitlich freigegeben werden, wobei bei maskiertem Arbeiten wahlweise die im Maskenregister (M-REG) enthaltene oder eine von außen zugeführte Bitstrukturmaske (EXT-BIT) von der Maskensteuerung (M-ST) bereitgestellt wird, oder aber durch die anhand eines besonderen Steuersignales (M) die Verknüpfungseinheit (AVL...) gesperrt wird.
31. Hybrid-Assoziativspeicher nach Anspruch 30, bei dem die Maskensteuerung (M-ST) einen Auswahlschalter (DEMUX) zur Ableitung des Steuersignales (M) aufweist, dessen Eingänge einerseits mit den Ausgängen des Maskenregisters (M-REG) und andererseits mit der Treffersignalleitung (T) der eigenen Verknüpfungseinheit (ALV...) sowie mit einer weiteren externen Signalleitung (EXT-BYT) verbunden sind, so daß das Sperrsignal (M) wahlweise von einem äußeren Sperrsignal (EXT-BYT), von dem bei der Durchführung einer Assoziationsrelation von der Verknüpfungseinheit (ALV) zuvor selbst ermittelten Treffersignal (T) oder aber von einem Bit der im Maskehregister (M-REG) enthaltenen Bitstrukturmaske ableitbar ist.
32. Hybrid-Assoziativspeicher nach Anspruch 31, g e k e n n z e i ch n e t durch ein zusätzliches extern ladbares zentrales Maskenregister für die Freigabe oder Sperrung der einzelnen Verknüpfungseinheiten (ALV) der assoziativen Oberfläche (ASS-FL) mit jeweils einem Informationsbit für jede Verknüpfungseinheit (ALV...) und individuellen Signalleitungen (EXT-BYT) zu den einzelnen Maskiersteuerungen (M-ST).
33. Hybrid-Assoziativspeicher nach einem der Ansprüche 17 bis 32, g e k e n n z e i c h n e t durch Einrichtungen (TS) zur gleichzeitigen Weiterleitung der Inhalte der Ergebnisregister (C-REG) aller Verknüpfungseinheiten (ALV...) der assoziativen Oberfläche (ASS-FL) in durch eine einheitliche Adresse ansteuerbare und als Hilfsspeicher vorgesehene Dateneinheitsebene des Basisspeichers (B-SP) mit Beibehaltung der individuellen Zuordnung zu den einzelnen Verknüpfungseinheiten (ALV...).
34. Hybrid-Assoziativspeicher nach einem der Ansprüche 1 bis 33, bei dem die mit allen Verknüpfungseinheiten (ALV...) der assoziativen Oberfläche (ASS-FL) verbundene Trefferauswertesteuerung (T-AUSW) je Verknüpfungseinheit (ALV...) wenigstens eine Kippstufe zur Trefferkettung aufweist und diese Kippstufen ein Schieberegister (T-SREG) bilden, dessen Inhalt beim Übergang von einer geketteten Datenteilfolge (z.B. DF0) auf die nachfolgende, durch eine andere Verknüpfungseinheit zu überprüfende Datenteilfolge (DF1) zur Aufrechterhaltung der Trefferkettung zyklisch um einen Schritt in der entsprechenden Richtung verschiebbar ist, und bei dem eine weitere Speichereinrichtung (KZ) zur Kennzeichnung der Anzahl der insgesamt vorgenommenen Verschiebeschritte für die Ermittlung des Speicheranfangs für die am Schluß eines Suchvorganges aufgefundenen Daten vorgesehen ist.
35. Hybrid-Assoziativspeicher nach einem der Ansprüche 1 bis 34, bei dem die mit allen Verknüpfungseinheiten (ALV...) der assoziativen Oberfläche (ASS-FL) verbundene Trefferauswertesteuerung (T-AUSW) Einrichtungen (T-SUM) zur Ermittlung der Anzahl der während einer durchgeführten Assoziationsrelation von allen Verknüpfungseineinheiten angezeigten Treffer (T_GES) aufweist.
36. Hybrid-Assoziativspeicher nach Anspruch 35, bei dem die Trefferauswertesteuerung (T-AUSW) Einrichtungen (T-SUM) zur Ermittlung der Gesamtzahl der während einer Folge von Assoziationsrelationen von den Verknüpfungseinheiten (ALV...) der assoziativen Oberfläche (ASS-FL) angezeigten Treffer (T_{GES (n)}) aufweist.
37. Hybrid-Assoziativspeicher nach einem der Ansprüche 1 bis 36, g e k e n n z e i c h n e t durch gesondert adressierbare Hilfsspeicher (PAR-SP) zur Bereitstellung der von den Verknüpfungseinheiten (ALV...) der assoziativen Oberfläche (ASS-FL) zur Überprüfung einer zugeführten Datenfolge jeweils benötigten unterschiedlichen Parameter (z.B. Suchargument, Bitstrukturmaske, Operanden) einheitlich für alle Verknüpfungseinheiten (AVL...).
38. Hybrid-Assoziativspeicher nach Anspruch 37, bei dem wenigstens einige der Hilfsspeicher für die Para- meter einen einheitlichen Speicher (PAR-SP) bilden, der wie der Basisspeicher (B-SP) bezüglich einer Gruppe von Dateneinheiten organisiert ist und in gleicher Weise Adressenumordner und Datenumordner für die richtige ZuOrdnung aufweist, wobei die Parameter jeweils derselben Art als Subeinheit von Parameter-Dateneinheiten zusammengefaßt extern bereitgestellt und im normalen Speicherbetrieb übernommen werden und die für jede Assoziationsrelation benötigten verschiedenen Parameter im assoziativen Betrieb jeweils gleichzeitig gelesen und den Verknüpfungseinheiten (AVL...) zur Verfügung gestellt werden.
39. Hybrid-Assoziativspeicher nach einem der Ansprüche 1 bis 38, g e k e n n z e i c h n e t durch einen
Sortierbitmuster-Generator (SBM-GEM) zur Erzeugung der jeweils beim Sortieren von im Basisspeicher (B-SP) gespeicherten Daten benötigten Sortierbitmuster (SBM) abhängig von den Ergebnissen der Trefferauswertesteuerung (T-AUSW), durch einen Speicher (SBM-SP) für die Zwischenspeicherung von der Arbeitsbreite der Verknüpfungseinheiten (ALV...) entsprechenden Einheiten (z.B. Bytes des Sortierbitmusters (SBM) bei Erweiterung des Sortierbitmusters über eine Bytebreite hinaus, sowie durch Kennzeichnungsbits (SB) je Datum im Basisspeicher
(B-SP) zur Kennzeichnung von im Rahmen eines Sortiervorganges aussortierten Daten und durch Einrichtungen zum Schreiben, Lesen und Überwachen der Kennzeichnungsbits.
40. Hybrid-Assoziativspeicher nach einem der Ansprüche
1 bis 39, g e k e n n z e i c h n e t durch eine Ablaufsteuerung (SORT-ST/HAS-ST) zur Durchführung von Such- und Sortiervorgängen und zur Bereitstellung der jeweils benötigten Parameter und Steuersignale (CMD) abhängig von den Ergebnissen der Trefferauswertesteuerung (T-AUSW).
41. Hybrid-Assoziativspeicher nach Anspruch 39 und 40, bei dem neben den in die Verknüpfungseinheiten (ALV...) der assoziativen Oberfläche (ASS-FL) integrierten Kettungselementen (z.B. PH-FF0) und Kettungssteuerungen je Verknüpfungseinheit eine zusätzliche Kettungssteuerung (KG-ST) und je Datum der beim Sortieren zu prüfenden Datei im Basisspeicher (B-SP) ein gesondertes Kettungselement vorgesehen ist.
42. Hybrid-Assoziativspeicher nach Anspruch 41, bei dem die gesonderten Kettungselemente aus einem Speicherabschnitt, z.B. Register oder Zähler, für eine Kennzahl (BG-NR) zur Anzeige der jeweils gültigen Bytegrenze (z.B. BG2) des Sortierbitmusters (SBM) bestehen.
43. Hybrid-Assoziativspeicher nach einem der Ansprüche 39 bis 42, g e k e n n z e i c h n e t durch individuelle Markierbits je Datum im Basisspeicher (B-SP) zur Markierung der jeweils durch einen Treffer während eines Suchlaufs gekennzeichneten Daten und durch eine Überwachungssteuerung für diese Markierbits zur Freigabe der Prüfung durch die Verknüpfungseinheiten (ALV...) bzw. zur Umsteuerung auf das jeweils nachfolgende Datum im Basisspeicher.
44. Hybrid-Assoziativspeicher nach einem der Ansprüche 39 bis 42, g e k e n n z e i c h n e t durch wenigstens einen zusätzlichen Adressenspeicher (T-AD-SP) für die Zwischenspeicherung der Adressen (T-AD) von durch Treffer der Verknüpfungseinheit gekennzeichneten Daten während eines Suchlaufes und durch Einrichtungen zur Übernahme der zwischengespeicherten Adressen (T-AD) für die Auswahl der zugehörigen Daten im Basisspeicher (B-SP).
45. Hybrid-Assoziativspeicher nach einem der Ansprüche 39 bis 44, bei dem der Basisspeicher (B-SP) wenigstens einen gesonderten Speicherbereich als Hilfsspeicher (H-SP) mit einer Kapazität für eine der Gesamtzahl der Verknüpfungseinheiten (ALV...) der assoziativen Oberfläche (ASS-FL) entsprechende Anzahl von Daten zur
Aufnahme von durch Treffern der assoziativen Oberfläche gekennzeichneten Daten aus den übrigen Bereichen des Basisspeichers (B-SP) im Rahmen eines Sortiervorganges für eine nachfolgende Bearbeitung (z.B. Endsortierung) durch die assoziative Oberfläche (ASS-FL) aufweist.
46. Verfahren zum Aufsuchen von Daten aus in einem Basisspeicher (B-SP) eines Hybrid-Assoziativspeichers nach einem der Ansprüche 1 bis 45 gespeicherten Datenfolgen oder Datenteilfolgen, die aus gleich großen Einheiten als Prüfeinheiten, z.B. Zeichen oder Byte zu je acht Bit, in beliebiger Kombination zusammengesetzt und jeweils einer Verknüpfungseinheit (ALV...) der assoziativen Oberfläche (ASS-FL) zugeordnet sind, anhand eines vorgegebenen Suchargumentes (ARG/SBM), d a d u r c h g e k e n n z e i c h n e t , daß zu Beginn eines jeden Suchvorganges von einem vorgegebenen Startschritt ausgehend die miteinander korrespondierenden Zeichen aller Datenfolgen oder Datenteilfolgen (z.B. DF0 und F1) jeweils parallel durch die jeweils zugehörige Verknüpfungseinheit (ALV...) anhand jeweils einheitlicher Parameter (PAR) mit den ersten Zeichen, z.B. A, des Suchargumentes (ARG/SSM) überprüft werden und diese Prüfung entlang der Datenfolgen (z.B. DF0 und DF1 ) fortgesetzt wird, bis ein Treffer erkannt wird, daß beim Suchen von aus mehreren Einheiten (z.B. A bis L) bestehenden Daten mit Erkennen des ersten Treffers für eine der Datenfolgen (z.B. DF0) die Trefferkettung der zugehörigen Verknüpfungseinheit (ALV...) wirksam geschaltet wird und alle nachfolgenden Zeichen der zugehörigen Datenfolgen (z.B. DF0) mit dem jeweils zugehörigen fortlaufenden Zeichen (z.B. B bis L) des Suchargumentes (ARG/SBM) überprüft werden, bis entweder alle Zeichen des Suchargumentes abgearbeitet sind oder aber für keine der überprüften Datenfolgen noch ein Treffer angezeigt wird, daß beim Ausbleiben eines Treffersignales für alle Datenfolgen nach Wirksamschalten der Trefferkettung der jeweils laufende Suchvorgang augenblicklich abgebrochen und ein neuer Suchvorgang mit um ein Zeichen gegenüber dem bisherigen Startschritt verschobenen Startschritt für den Basisspeicher (B-SP) eingeleitet wird und daß das Wechselspiel zwischen Einleiten eines Suchvorganges und fortlaufender Prüfung mit Trefferkettung notfalls solange wiederholt wird, bis alle Datenfolgen mit jeweils verschobenem Suchargument überprüft sind.
47. Verfahren nach Anspruch 46, d a d u r c h g e k e n n z e i c h n e t , daß bei miteinander geketteten Datenteilfolgen (z.B. DF0 und DF1) jeweils mit Erreichen des Endes der Datenteilfolgen bei über das Ende der Datenteilfolgen hinausgehendem Suchargument (ARG/SBM) die Prüfung in zyklischer Folge mit den Anfängen der Datenteilfolgen fortgesetzt wird und daß die jeweils bis zum Ende einer Datenteilfolge durch die zugehörige Verknüpfungseinheit (ALV...) gewonnenen Treffer mit den nachfolgend durch eine benachbarte Verknüpfungseinheit gewonnenen Treffern für die zyklisch nachfolgende Datenteilfolge (z.B. DF1) gekettet werden.
48. Verfahren zum Aufsuchen von im Basisspeicher (B-SP) eines Hybrid-Assoziativspeichers nach einem der Ansprüche 1 bis 45 gespeicherten Daten ausgerichteter Dateien abhängig von dem den einzelnen Daten zugeordneten Rang, z.B. zum Sortieren der Daten, die aus gleich großen Einheiten, z.B. Zeichen oder Byte zu je acht Bit, in beliebiger Kombination zusammengesetzt sind, wobei jeweils eine Gruppe von Daten jeweils einer Verknüpfungseinheit (ALV...) der assoziativen Oberfläche (ASS-FL) zugeordnet ist, der die Zeichen der Daten nacheinander zugeführt werden, so daß mehrere Gruppen von Daten gleichzeitig zeichenweise durch die assoziative Oberfläche (ASS-FL) überprüfbar sind, d a d u r c h g e k e n n z e i c h n e t , daß die jeweils ersten Zeichen (z.B. A1, B1 bis X1) eines jeden Datums bei innerhalb des ersten Byte des Sortierbitmusters (SBM) liegendem Ausgangspunkt für einen Sortiervorgang anhand jeweils einheitlicher Parameter (PAR) und des gewählten Sortierbitmusters (SBM) in einem ersten Suchlauf (SL1) überprüft werden, daß abhängig von der Treffergesamtzahl (= 0, = 1, > 1) des Suchlaufes das Sortierbitmuster (SBM) und ggf. eine Maske (SBM-MASK) für die Festlegung des Assoziationsbereiches zu Beginn der weiteren Suchläufe jeweils bitweise eingeengt oder erweitert werden, wobei während eines Suchlaufes zum Aussortieren gefundene Daten ggf. aussortiert und als solche gekennzeichnet werden, daß bei Erweiterung des Sortierbitmusters (SBM) über die Bytegrenzen (z.B. BG1, BG2) hinaus bei jeder Bytegrenzenüberschreitung das jeweils zuletzt gültige vollständige Byte des Sortierbitmusters zwischengespeichert wird, daß bei über die Bytegrenze (BG1) ausgeweitetem Sortier bitmuster (SBM) in jedem Suchlauf vor Überprüfen mit dem jeweils aktuellen Byte des Sortierbitmusters alle möglicherweise vorangehenden Zeichen des jeweils zu prüfenden Datums anhand der zwischengespeicherten Bytes des Sortierbitmusters nacheinander überprüft und die dabei erhaltenen Treffer je Zeichen miteinander gekettet werden, sowie die Überprüfung mit dem aktuellen Byte des Sortiermusters nur dann ausgeführt wird, wenn die Kettungsbedingung für die abgespeicherten Bytes des Sortierbitmusters für das jeweils zu prüfende Datum erfüllt ist.
49. Verfahren nach Anspruch 48, d a d u r c h g e k e n n z e i c h n e t , daß der bei Ausweitung des Sortierbitmusters (SBM) an einer überschrittenen Bytegrenze (z.B. BG2) bestehende Kettungszustand in einem dem jeweiligen Datum zugeordneten Kettungselement jeweils gespeichert wird, daß während der nach jeder Bytegrenzenüberschreitung durchgeführten Suchläufe (SL...) Prüfungen lediglich mit dem aktuellen Byte des Sortierbitmusters (SBM) durchgeführt und sich dabei ergebende Treffer lediglich in Verbindung mit einer zugehörigen gültigen Kettungsanzeige (KG) gewertet werden und daß dagegen bei jeder Unterschreitung einer Bytegrenze (z.B. BG2) des Sortierbitmusters (SBM) zunächst für alle Daten die Kettungsanzeige (KG) für die neue gültige Bytegrenze (z.B. BG1) in den zugehörigen Kettungselementen neu ermittelt wird und erst dann mit dem jeweils aktuellen Byte des Sortierbitmusters die Suchlaufe fortgesetzt werden.
50. Verfahren nach Anspruch 49, d a d u r c h g e k e n n z e i c h n e t , daß als Kettungsanzeige eine Kennzahl der jeweils letzten gültigen Bytegrenze (z.B. BG2) verwendet wird, daß bei jeder Unterschrei- tung einer Bytegrenze (z.B. BG2) des Sortierbitmusters (SBM) zunächst die Kennzahlen aller nicht bereits aussortierten Daten der Datei im Basisspeicher (B-SP) mit der zwischengespeicherten Anzahl vollständiger Bytes des Sortierbitmusters (SBM) verglichen werden und bei Gleichheit die Kennzahl um eine Einheit verringert wird, während bei Ungleichheit die Kennzahl unverändert bleibt, und daß bei den nachfolgenden Suchläufen sich ergebende Treffer lediglich in Verbindung mit einer die gültige Bytegrenze zum aktuellen Byte des Sortierbitmusters anzeigenden Kennzahl gewertet werden.
51. Verfahren nach Anspruch 50, d a d u r c h g e k e n n z e i c h n e t , daß die Kennzahl für die jeweils letzte gültige Bytegrenze (z.B. BG2) der einzelnen Daten und der jeweilige Vergleichswert für die Bytekettung des Sortierbitmusters (SBM) von zentralen Steuerregistern (z.B. Adressenregistern des Sortierbitmusterspeichers) abgeleitet werden.
52. Verfahren nach einem der Ansprüche 48 bis 51, d a d u r c h g e k e n n z e i c h n e t , daß bei Auftreten eines zweiten Treffers innerhalb eines Suchlaufes mit dem jeweils aktuellen Byte des Sortierbitmusters (SBM) dieser unmittelbar abgebrochen und das Sortierbitmuster erweitert wird.
53. Verfahren nach einem der Ansprüche 48 bis 51, d a d u r c h g e k e n n z e i ch n e t , daß die während eines Suchlaufs zu Treffern führenden Daten markiert werden und daß bei mehreren während eines Suchlaufs erzielten Treffern im nachfolgenden Suchlauf lediglich die von markierten Daten herrührenden Treffer berücksichtigt werden.
54. Verfahren nach Anspruch 53, d a d u r c h g e k e n n z e i c h n e t , daß die markierten Daten anhand der Markierungen ermittelt und nur diese Daten einer Prüfung unterzogen werden.
55. Verfahren nach Anspruch 53, d a d u r c h g e k e n n z e i c h n e t , daß die Adressen (T-AD) der zu Treffer führenden Daten gesondert zwischengespeichert werden und daß während des bzw. der nachfolgenden Suchläufe die zu überprüfenden Daten anhand der zwischengespeicherten Adressen (T-AD) ermittelt und aussortiert werden.
56. Verfahren nach einem der Ansprüche 48 bis 51, d a d u r c h g e k e n n z e i c h n e t , daß die während eines Suchlaufes durch Treffer gekennzeichneten Daten in einen assoziativen Hilfsspeicher (H-SP) übernommen und im Datenspeicher (B-SP) als aussortiert markiert werden, daß die in den Hilfsspeicher übernommenen Daten jeweils in gleicher Weise durch Treffer gesteuerte Einstellung von Sortierbitmuster (SBM) und ggf. Maske (SBM-MASK) endsortiert und ausgegeben werden und daß jeweils danach ein neuer Suchlauf für den Datenspeicher (B-SP) eingeleitet wird, bis alle gewünschten Daten aussortiert sind.
57. Verfahren nach Anspruch 56, d a d u r c h g e k e n n z e i c h n e t , daß die während eines jeden Suchlaufes insgesamt angefallene Anzahl von Treffern ermittelt und auf die Einhaltung eines vorgegebenen Größenbereichs überwacht wird, daß durch schrittweise erfolgendes Einstellen von Sortierbitmuster (SBM) und ggf. (SBM-MASK) aufgrund der jeweils vorangehend ermittelten Trefferanzahl die Anzahl der bei jedem neuen Suchlauf gewonnenen Treffer so beeinflußt wird, daß diese mit dem vorgegebenen Größenbereich übereinstimmt, und daß erst dann die während eines nachfolgenden Suchlaufs unveränderten Sortierbitmuster (SBM) zu einem Treffer führenden Daten in den Hilfsspeicher (H-SP) übernommen werden.
58. Verfahren nach Anspruch 56 oder 57, d a d u r c h g e k e n n z e i c h n e t , daß bei Verwendung eines Hilfsspeichers (H-SP (H-SP) mit nur einem Datum je Verknüpfungseinheit (ALV...) als Speicherkapazität ein Austausch der Dateneinheiten zwischen Hilfsspeicher und den Verknüpfungseinheiten lediglich bei Überschreiten einer Bytegrenze des Sortierbitmusters (SBM) erfolgt, daß jeder auf einen Prüfvorgang reduzierte Suchlauf bei einem Mehrfachtreffer ( > 1 ) abgebrochen und mit neuer Sortierbitmuster- und ggf. Maskeneinstellung wieder neu begonnen wird und daß infolge von Einzeltreffern (= 1) ausgegebene Daten eine Sperrung der zugehörigen Verknüpfungseinheit (ALV) bewirken.
59. Verfahren nach einem der Ansprüche 48 bis 58, d a d u r c h g e k e n n z e i c h n e t , daß statt einer Assoziationsfunktion "GLEICH" mit Maskenabdeckung der nicht relevanten Bitstellen des Sortierbitmusters (SBM) eine Assoziationsfunktion
"KLEINER/GLEICH" beim Vorwärts- oder Aufwärts-Sortieren bzw. "GRÖSSER/GLEICH" beim Rückwärts- oder Abwärtssortieren verwendet wird und daß bei einer vorgegebenen Arbeitsbreite zur Ausführung der einzelnen Assoziationsfunktionen durch die Verknüpfungseinheit (ALV) die für das Sortierbitmuster (SBM) nicht relevanten Bitstellen abhängig von der Sortierrichtung auf "1" bzw. "0" gesetzt werden.
60. Verfahren nach einem der Ansprüche 48 bis 59 zur Ermittlung von Einzeldaten oder einer vorgegebenen Anzahl von Daten aus einer Datenmenge mit dem Höchst- bzw. Mindestwert oder mit den höchsten bzw. niedrigsten Werten, d a d u r c h g e k e n n z e i c h n e t , daß ausgehend von einem die volle Arbeitsbreite zur Ausführung von Assoziationsfunktionen abdeckenden Sortierbitmuster (SBM) mit dem Ausgangswert "11...11" bzw. "00...00" der Sortiervorgang durchgeführt wird, bis ein erster oder die vorgegebene Anzahl von Sortiertreffern beim Sortieren in Rückwärts- bzw. Vorwärtsrichtung erzielt ist.
61. Verfahren nach einem der Ansprüche 48 bis 59 zur Ermittlung von Einzeldaten oder einer vorgegebenen Anzahl von Daten mit einem zu einem vorgegebenen Bezugswert am nächsten liegenden Wert, d a d u r c h g e k e n n z e i c h n e t , daß mit dem Bezugswert als Sortierbitmuster (SBM) in einem Ausscheidungslauf zunächst alle Daten der zu prüfenden Datenmenge überprüft und abhängig von der Bezugsrichtung (z.B. Aufwärts- bzw. Abwärts) der zu ermittelnden Daten zum Bezugswert alle Daten als aussortiert gekennzeichnet werden, deren Wert kleiner bzw. größer ist als der Bezugswert und daß erst anschließend ausgehend von dem Bezugswert als Sortierbitmuster (SBM) der Sortiervorgang anhand der nicht als aussortiert gekennzeichneten Daten durchgeführt wird, bis ein erster oder die vorgegebene Anzahl von Sortiertreffern beim Sortieren in Vorwärts- bzw. Rückwärtsrichtung erzielt ist.

类似技术:

---

公开号 | 公开日 | 专利标题

---

US5519857A|1996-05-21|Hierarchical presearch type text search method and apparatus and magnetic disk unit used in the apparatus

---

US5197135A|1993-03-23|Memory management for scalable compound instruction set machines with in-memory compounding

---

CN106447035A|2017-02-22|具有可变率执行单元的处理器

---

CN104636274B|2018-01-26|数据预取方法以及微处理器

---

DE69434967T2|2008-01-17|Programmumsetzungseinheit und verbesserter Prozessor für Adressierung

---

US4357678A|1982-11-02|Programmable sequential logic array mechanism

---

US4606002A|1986-08-12|B-tree structured data base using sparse array bit maps to store inverted lists

---

US8335098B2|2012-12-18|Memory device including OTP memory block and pseudo MTP memory block and memory access method

---

US5222235A|1993-06-22|Databases system for permitting concurrent indexing and reloading of data by early simulating the reload process to determine final locations of the data

---

EP0961211B1|2005-07-27|Datenbankverfahren und -vorrichtung mit hierarchischer, auf Bitvektor basierender Indexstruktur

---

US7953955B2|2011-05-31|Methods and apparatus for automated generation of abbreviated instruction set and configurable processor architecture

---

US6845024B1|2005-01-18|Result compare circuit and method for content addressable memory | device

---

CN102110058B|2016-01-13|一种低缺失率、低缺失惩罚的缓存方法和装置

---

US4438493A|1984-03-20|Multiwork memory data storage and addressing technique and apparatus

---

US5440709A|1995-08-08|Apparatus and method for an improved content addressable memory using a random access memory to generate match information

---

US5072422A|1991-12-10|Content-addressed memory system with word cells having select and match bits

---

US6243281B1|2001-06-05|Method and apparatus for accessing a segment of CAM cells in an intra-row configurable CAM system

---

US6411957B1|2002-06-25|System and method of organizing nodes within a tree structure

---

AU624205B2|1992-06-04|Variable length string matcher

---

DE3801380C2|1991-02-21|

---

US4972316A|1990-11-20|Method of handling disk sector errors in DASD cache

---

US3800292A|1974-03-26|Variable masking for segmented memory

---

JP2851665B2|1999-01-27|データ圧縮システム

---

US4580240A|1986-04-01|Memory arrangement operable as a cache and a local memory

---

DE69636761T2|2007-04-05|Speichern und wiederauffinden von geordneten schlüsselmengen in einem kompakten 0-kompletten baum

同族专利:

---

公开号 | 公开日

---

US4799149A|1989-01-17|

引用文献:

---

公开号 | 申请日 | 公开日 | 申请人 | 专利标题

---

DE1424741A1|1960-01-11|1969-03-20|Rca Corp|Einrichtung zum Durchsuchen eines Speichers|

---

US3307153A|1962-06-16|1967-02-28|Int Standard Electric Corp|Method of performing on-the-fly searches for information stored on tape storages or the like|

---

DE2342660A1|1973-08-23|1975-03-06|Siemens Ag|Verfahren und anordnung zum sortieren von daten|

---

DE2547052A1|1975-07-22|1977-06-16|Int Computers Ltd|Datenverarbeitungseinrichtung|

---

US4257110A|1977-04-19|1981-03-17|Semionics Associates, Inc.|Recognition memory with multiwrite and masking|

---

US4163281A|1977-06-30|1979-07-31|Elettronica San Giorgio Elsag S.P.A.|Method and apparatus for the rotation of a binary-data matrix, intended particularly to be used as a storage unit having a two-way access mode for electronic computers|

---

US4153943A|1977-08-12|1979-05-08|Honeywell Inc.|High speed I/O for content addressable type memories|

---

EP0035787A2|1980-03-11|1981-09-16|Siemens Aktiengesellschaft|Hybrid-Assoziativspeicher und dessen Anwendungen, insbesondere zum Sortieren von gespeicherten Daten|

---

EP0036148A1|1980-03-11|1981-09-23|Siemens Aktiengesellschaft|Hybrid-Assoziativspeicher|

---

EP0048056A1|1980-09-12|1982-03-24|Philips Electronics N.V.|Gerät zum sequentiellen Verarbeiten von Datenaufzeichnungen|

---

EP0047842A2|1980-09-15|1982-03-24|International Business Machines Corporation|Adressengenerator für eine versetzte Matrix|

---

DE3216905A1|1982-05-06|1982-11-18|Alfred Dipl Ing Schraufstetter|Assoziativer subprozessor in einer busorientierten datenverarbeitungsanlage|EP0371488A2|1988-11-29|1990-06-06|Matsushita Electric Industrial Co., Ltd.|Dynamischer Video-RAM-Speicher|

---

USRE35921E|1988-11-29|1998-10-13|Matsushita Electric Industrial Co., Ltd.|Dynamic video RAM incorporating single clock random port control|US3648254A|1969-12-31|1972-03-07|Ibm|High-speed associative memory|

---

US3757312A|1970-10-09|1973-09-04|Us Navy|General purpose associative processor|

---

US3771139A|1971-05-03|1973-11-06|D Digby|Associative memory method of performing simultaneous content searches|

---

US3742460A|1971-12-20|1973-06-26|Sperry Rand Corp|Search memory|

---

US3906455A|1974-03-15|1975-09-16|Boeing Computer Services Inc|Associative memory device|

---

US3958222A|1974-06-27|1976-05-18|Ibm Corporation|Reconfigurable decoding scheme for memory address signals that uses an associative memory table|

---

GB1540996A|1975-05-12|1979-02-21|Plessey Co Ltd|Associative processors|

---

US4144564A|1977-04-19|1979-03-13|Semionics Associates|Associative memory|

---

US4149262A|1977-04-19|1979-04-10|Semionics Associates|Associative memory device with variable recognition criteria|

---

US4145737A|1977-04-19|1979-03-20|Semionics Associates|Associative memory device with time shared comparators|

---

US4280177A|1979-06-29|1981-07-21|International Business Machines Corporation|Implicit address structure and method for accessing an associative memory device|US5261046A|1988-12-27|1993-11-09|Eastman Kodak Company|Resequencing line store device|

---

JPH02178730A|1988-12-28|1990-07-11|Toshiba Corp|Internal sorting system using dividing method|

---

US5051894A|1989-01-05|1991-09-24|Bull Hn Information Systems Inc.|Apparatus and method for address translation of non-aligned double word virtual addresses|

---

US5361328A|1989-09-28|1994-11-01|Ezel, Inc.|Data processing system using a neural network|

---

JP2724374B2|1989-10-11|1998-03-09|シャープ株式会社|データ処理装置|

---

US5222234A|1989-12-28|1993-06-22|International Business Machines Corp.|Combining search criteria to form a single search and saving search results for additional searches in a document interchange system|

---

JPH0831276B2|1990-06-15|1996-03-27|松下電器産業株式会社|半導体メモリ|

---

US5278987A|1991-03-05|1994-01-11|Franklin Chiang|Virtual pocket sorting|

---

DE69325786T2|1992-12-04|2000-02-17|Koninkl Philips Electronics Nv|Prozessor für gleichförmige Operationen auf Datenreihenfolgen in entsprechenden parallelen Datenströmen|

---

TW207013B|1993-02-19|1993-06-01|Nat Science Committee|Architecture of optimal high-speed sorter|

---

KR100218523B1|1995-10-12|1999-09-01|윤종용|엠펙 비디오 복호기|

---

DE19837101C2|1998-08-17|2000-11-23|Philips Corp Intellectual Pty|Programmierbare 1-Bit Datenverarbeitungsanordnung|

---

US7233970B2|2001-05-02|2007-06-19|Cipher Corporation Limited|Computational method, system, and apparatus|

---

US8024392B2|2002-02-16|2011-09-20|Ncipher Corporation Limited|Computational method, system, and apparatus|

---

US6910095B2|2001-10-01|2005-06-21|Britestream Networks, Inc.|Memory request handling method for small discontiguous accesses to high-density memory devices|

---

US7218734B2|2001-05-02|2007-05-15|Nciper Corporation Limited|Ring arithmetic method, system, and apparatus|

---

US7913261B2|2001-05-02|2011-03-22|nCipher Corporation, Ltd.|Application-specific information-processing method, system, and apparatus|

---

US6738874B2|2001-05-02|2004-05-18|Layer N Networks, Inc.|Controller architecture and strategy for small discontiguous accesses to high-density memory devices|

---

JP4346975B2|2003-06-27|2009-10-21|株式会社ルネサステクノロジ|連想メモリ機能付き集積回路及び侵入検知装置|

---

US7266635B1|2004-07-22|2007-09-04|Marvell Semiconductor Israel Ltd.|Address lookup apparatus having memory and content addressable memory|

---

US7457937B1|2005-02-09|2008-11-25|Nvidia Corporation|Method and system for implementing low overhead memory access in transpose operations|

---

JP2006260981A|2005-03-17|2006-09-28|Shin Kobe Electric Mach Co Ltd|バッテリコントローラ|

---

TWM326186U|2007-06-13|2008-01-21|Princeton Technology Corp|Device for data be written into memory|

---

KR101979392B1|2012-05-17|2019-05-16|삼성전자주식회사|불휘발성 메모리 장치 및 그것의 프로그램 방법|

---

US9715343B2|2013-12-09|2017-07-25|International Business Machines Corporation|Multidimensional partitioned storage array and method utilizing input shifters to allow multiple entire columns or rows to be accessed in a single clock cycle|

---

US9442661B2|2013-12-09|2016-09-13|International Business Machines Corporation|Multidimensional storage array and method utilizing an input shifter to allow an entire column or row to be accessed in a single clock cycle|

法律状态:
1984-10-11| AK| Designated states|Designated state(s): JP US |

---

1985-01-17| COP| Corrected version of pamphlet|

优先权:

---

申请号 | 申请日 | 专利标题

---